Finden Sie einen negativen Zyklus mit Scheitelpunktbeschränkungen

Wie können wir bei einem Diagramm mit gewichteten Kanten einen negativen Zyklus finden, der mindestens einen Scheitelpunkt in einer bestimmten Scheitelpunktmenge ? Vielen Dank.$\{V_1, V_2, \ldots, V_k\}$

Wenn der Zyklus nicht einfach sein soll, teilen Sie den (gerichteten) Graphen in seine stark verbundenen Komponenten auf und prüfen Sie für jede Komponente, die einen der angegebenen Eckpunkte , ob die Komponente einen negativen Zyklus enthält. Wenn keine Komponente vorhanden ist, gibt es keinen negativen Zyklus, der . Wenn dies bei einer Komponente der Fall ist, können Sie einen (nicht einfachen) negativen Zyklus finden, der enthält, indem Sie viele Kopien des negativen Zyklus erstellen und diesen Pfaden zu und von einem Scheitelpunkt im Zyklus zu hinzufügen . (Die Gesamtzeit zum Finden einer impliziten Darstellung des gewünschten Zyklus entspricht der Zeit zum Finden eines negativen Zyklus in einem gerichteten Graphen, z. B. , wenn ich mich recht erinnere.)$V_i$$V_i$$V_i$$V_i$$O(nm)$

Wenn der Zyklus einfach sein muss, ist das Problem NP-vollständig, selbst wenn nur ein einziger Scheitelpunkt angegeben ist. (Sie können den Hamilton-Pfad auf das Problem reduzieren: Um einen Hamilton-Pfad von einer bestimmten Quelle zu einer bestimmten Senke in einem bestimmten Diagramm , geben Sie das vorhandene Kantengewicht -1 an und fügen Sie dann einen künstlichen Scheitelpunkt mit zwei Kostenkanten hinzu jeweils eine von bis und eine von bis .)$V_1$$S$$T$$G$$V_1$$N/2-0.01$$V_1$$S$$T$$V_1$

Wenn Sie zulassen, dass der Zyklus Scheitelpunkte, aber keine Kanten wiederholt, ist er meiner Meinung nach immer noch NP-vollständig (durch eine ähnliche Reduzierung, aber die Aufteilung jedes Scheitelpunkts in eine gerichtete Kante auf standardmäßige Weise).$v$$(v,v')$

Ich gehe davon aus, dass Ihre Eingabe ein gerichteter Graph ist. Ich weiß nicht, wie ich das für den ungerichteten Fall machen soll.

Erstellen Sie Kopien des Scheitelpunktsatzes Ihres Diagramms, wobei die Anzahl der Scheitelpunkte im Diagramm ist. Ersetzen Sie jede Kante von nach in Ihrem Originaldiagramm durch Kanten, die von Kopie von zu Kopie von reichen , für alle Auswahlmöglichkeiten von . Wenn zur angegebenen Scheitelpunktmenge gehört, aber nicht anders, schließen Sie außerdem eine Kante ein, die von Kopie von zu Kopie von .$n$$n$$u$$v$$i$$u$$i+1$$v$$i$$u$$i$$u$$0$$v$

Die Zyklen im erweiterten Diagramm werden alle auf Zyklen im ursprünglichen Diagramm zurückprojiziert, aber jeder Zyklus im erweiterten Diagramm enthält einen der angegebenen Scheitelpunkte (andernfalls können Sie die Erweiterungsebenen nicht rückwärts durchlaufen), sodass das ursprüngliche Diagramm enthält Ein negativer Zyklus, der einen bestimmten Scheitelpunkt enthält, wenn der erweiterte Graph einen negativen Zyklus enthält.