Ist das NP-schwer? Ich kann es nicht beweisen.

11

Ich habe ein Problem und ich denke, es ist NP-schwer, aber ich kann es nicht beweisen.

Hier ist ein Ebenendiagramm, wobei Schicht 0 die höchste Schicht und Schicht L die niedrigste ist.

Es gibt einige gerichtete Kanten zwischen Schichten, wobei eine Kante (A, B) anzeigt, dass Knoten A Knoten B [abdecken] kann. Und wenn A B abdecken kann, kann jeder Knoten auf einem beliebigen Pfad von A nach B B abdecken, B kann abdecken selbst.

Schließlich kommt hier eine Menge von Knoten S. Ich muss eine andere Menge von Knoten ANS auswählen und sicherstellen, dass für jeden Knoten q in S ein Knoten p in ANS existiert und p q abdeckt.

Für jeden Knoten fallen Kosten an, und ich muss die Gesamtkosten für das Festlegen von ANS minimal halten.

Ist das ein NP-hartes Problem? Ich denke schon, aber ich kann es nicht beweisen.

Kannst du mir helfen?

Vielen Dank.

graphs np qin.sun
quelle
Die Kosten für den Knoten aus der oberen Schicht sind in jedem Pfad des Diagramms teurer.
Ja, es scheint in der Tat NP schwer. Schauen Sie sich das ähnliche Problem mit der minimalen Set-Abdeckung an. en.wikipedia.org/wiki/Set_cover_problem
Gibt es eine Einschränkung in der gerichteten Kante, z. B. verbinden die Kanten nur einen Knoten in einer höheren Schicht mit einem Knoten in einer niedrigeren Schicht? Kann ich klarstellen, dass zwischen Knoten in derselben Ebene keine Kante vorhanden sein darf?
halb
@justhalf Nein, es gibt keine Kante zwischen Knoten in derselben Ebene. Vielen Dank :)
qin.sun

Antworten:

6

Ja, dieses Problem ist definitiv NP schwer. Ich poste diese Antwort, da Sie einen Beweis benötigen.

Wenn Sie diesem Link folgen: http://en.wikipedia.org/wiki/Set_cover_problem , heißt es, dass die Optimierungsversion des minimalen Set-Cover-Problems NP-Hard ist.

Das Problem im Link:

Bei einer Menge von Elementen {1,2, ..., m} (genannt das Universum) und einer Menge S von n Mengen, deren Vereinigung gleich dem Universum ist, besteht das Problem der Mengenabdeckung darin, die kleinste Teilmenge von S zu identifizieren, deren Vereinigung gleich der ist Universum. Betrachten Sie zum Beispiel das Universum U = {1, 2, 3, 4, 5} und die Menge der Mengen S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Die Vereinigung von S ist eindeutig U. Wir können jedoch alle Elemente mit der folgenden, kleineren Anzahl von Mengen abdecken: {{1, 2, 3}, {4, 5}}

Sie können dies wie folgt mit Ihrem Problem in Verbindung bringen:

S ist die Menge von Knoten, die mindestens einen Knoten in Ihrer Eingabemenge abdecken. Dies kann durch Durchführen einer DFS an den Knoten des Eingabesatzes mit umgekehrter Kantenrichtung festgestellt werden.

Das im Link beschriebene Problem ist nun ein Sonderfall Ihres Problems, bei dem die Kosten für jeden Knoten gleich sind und Sie nur die Anzahl der Knoten (Sätze) minimieren möchten.

Daher ist Ihr Problem im allgemeinen Fall noch schwieriger zu lösen und daher NP Hard.

Abhishek Bansal
quelle
Ich denke, dass dies mit der Definition des OP zutrifft, aber er gibt auch nie an, ob Sie einen Knoten mit einer Kante in derselben Ebene wie dieser Knoten "abdecken" können. Wenn dies der Fall ist, scheint das Problem etwas anders zu sein. Andernfalls, wenn Sie einen Knoten nur über eine Kante aus einer höheren Ebene abdecken können, scheint dies in der Tat gleichbedeutend mit der Einstellung der Deckungsoptimierung zu sein
Roliu
@roliu Wie wäre es wichtig, ob die gleichen Schichtknoten abgedeckt werden können oder nicht. Das Problem, wie ich es verstehe, ist, dass wir einen gerichteten Graphen mit einem Pfad zwischen Knoten A und B haben, was bedeutet, dass A B abdeckt.
Hm, ich denke nicht sicher. Es ist nur seltsam, weil ich nicht denke, dass fast alle Informationen im OP tatsächlich nützlich sind. Die Schichten scheinen irrelevant zu sein, ebenso die Transitivität. Ich warte meistens nur darauf, dass der OP klarstellt, dass er tatsächlich etwas anderes gemeint hat. Insbesondere können Sie zeigen, dass es nicht nur mindestens so hart wie die festgelegte Abdeckung ist, sondern tatsächlich gleichwertig. Weil jede minimale Abdeckung im OP-Problem nur benachbarte Knoten seines Eingabesatzes enthält S. Vielleicht gibt es negative Kosten oder so etwas ...
Roliu