Est-ce NP-difficile? Je ne peux pas le prouver.

11

J'ai un problème et je suppose que c'est NP-difficile, mais je ne peux pas le prouver.

Voici un graphique de calque, où le calque 0 est le calque le plus chaud et le calque L le plus bas.

il y a un bord dirigé entre les couches, où un bord (A, B) indique que le nœud A peut [couvrir] le nœud B. Et quand A peut couvrir B, chaque nœud sur n'importe quel chemin de A à B peut couvrir B, B peut couvrir lui-même.

Enfin, voici un ensemble de nœuds S. J'ai besoin de choisir un autre ensemble de nœuds ANS, et de m'assurer que pour chaque nœud q dans S, il existe un nœud p dans ANS et p couvre q.

Pour chaque nœud, il y a un coût, et je dois minimiser le coût total de l'ensemble ANS.

Est-ce un problème NP-difficile? Je pense que oui mais je ne peux pas le prouver.

Pourriez-vous m'aider?

Merci beaucoup.

graphs np qin.sun
la source
le coût du nœud de la couche supérieure est plus cher dans n'importe quel chemin du graphique.
Oui, il semble en effet difficile NP. Regardez le problème de fermeture de la couverture minimale similaire. en.wikipedia.org/wiki/Set_cover_problem
Y a-t-il une restriction dans le bord dirigé, comme les bords ne connectent qu'un nœud dans la couche supérieure à un nœud dans la couche inférieure? Puis-je préciser qu'il ne peut y avoir de bord entre les nœuds dans la même couche?
Justhalf
@justhalf Non, il n'y a pas d'arête entre les nœuds de la même couche. Merci :)
qin.sun

Réponses:

6

Oui, ce problème est définitivement NP difficile. Je poste cette réponse car vous avez besoin d'une preuve.

Si vous suivez ce lien http://en.wikipedia.org/wiki/Set_cover_problem , cela indique que la version d'optimisation du problème de couverture d'ensemble minimal est NP-Hard.

Le problème dans le lien:

Étant donné un ensemble d'éléments {1,2, ..., m} (appelé l'univers) et un ensemble S de n ensembles dont l'union est égale à l'univers, le problème de la couverture d'ensemble est d'identifier le plus petit sous-ensemble de S dont l'union est égale à la univers. Par exemple, considérons l'univers U = {1, 2, 3, 4, 5} et l'ensemble des ensembles S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Il est clair que l'union de S est U. Cependant, nous pouvons couvrir tous les éléments avec le plus petit nombre d'ensembles suivants: {{1, 2, 3}, {4, 5}}

Vous pouvez associer cela à votre problème comme suit:

S est l'ensemble des nœuds qui couvrent au moins un nœud de votre ensemble d'entrée. Cela peut être trouvé en effectuant un DFS sur les nœuds de l'ensemble d'entrée avec la direction des bords inversée.

Maintenant, le problème décrit dans le lien est un cas particulier de votre problème, où le coût de chaque nœud est égal et où vous souhaitez simplement minimiser le nombre de nœuds (ensembles).

Par conséquent, votre problème est encore plus difficile à résoudre dans le cas général et c'est donc NP Hard.

Abhishek Bansal
la source
Je pense que cela est vrai avec la définition de l'OP, mais il ne précise jamais non plus si vous pouvez "couvrir" un nœud avec une arête dans la même couche que ce nœud. Si tel est le cas, le problème semble un peu différent. Sinon, si vous ne pouvez couvrir un nœud que via un bord d'une couche supérieure, cela semble en effet équivalent à définir l'optimisation de la couverture
roliu
@roliu Comment serait-il important que les mêmes nœuds de couche puissent être couverts ou non. Le problème que je comprends est que nous avons un graphe orienté avec un chemin entre le nœud A à B signifie que A couvre B.
Hm, pas sûr je suppose. C'est juste étrange parce que je ne pense pas que presque toutes les informations du PO soient réellement utiles. Les couches semblent non pertinentes, tout comme la transitivité. J'attends surtout que le PO clarifie qu'il voulait vraiment dire quelque chose de différent. En particulier, vous pouvez montrer que ce n'est pas seulement au moins aussi dur que la pochette, c'est en fait équivalent. Parce que toute couverture minimale dans le problème de l'OP ne contiendra que des nœuds voisins de son ensemble d'entrée S. Peut-être qu'il y a des coûts négatifs ou quelque chose comme ça ...
roliu