Minimaler M. Schnitt in gewichteten gerichteten azyklischen Graphen mit möglicherweise negativen Gewichten

9

Ich bin auf folgendes Problem gestoßen:

Berechnen Sie bei einem gerichteten azyklischen Graphen mit reellen Kantengewichten und zwei Eckpunkten s und t den minimalen M.-Schnitt.

Für allgemeine Diagramme ist dies NP-hart, da man den Maximalschnitt trivial reduzieren kann, indem man einfach die Kantengewichte umkehrt (korrigiere mich, wenn ich falsch liege).

Wie ist die Situation mit DAGs? Kann Min-Cut (oder Max-Cut) in Polynomzeit gelöst werden? Ist es NP-schwer und wenn ja, gibt es bekannte Approximationsalgorithmen?

Ich habe versucht, Arbeit zu finden, konnte dies aber nicht (vielleicht verwende ich bei meinen Suchanfragen nur falsche Schlüsselwörter), also hoffte ich, dass jemand etwas darüber weiß (oder findet).

George
quelle
2
Wo scheitert hier die lineare Programmierformulierung von Min-Cut?
Peter Shor
(unter Verwendung der Notation von en.wikipedia.org/wiki/… ): Für Kanten mit negativen Gewichten kann d_ {ij} beliebig groß sein. Selbst wenn man d_ {ij} von oben begrenzt, wird für Kanten mit negativen Gewichten immer der maximal mögliche Wert angenommen. Die Lösung für ein solches Programm ergibt also nicht immer einen gültigen Schnitt. Ich kann mich irren, da ich mit solchen Problemen nicht sehr erfahren bin. Wenn ja, korrigieren Sie mich bitte. Grundsätzlich möchte ich wissen, ob Max-Cut (mit beliebigen Gewichten) für DAGs effizient gelöst werden kann oder nicht.
George
1
Damit dies funktioniert, müssen Sie die erste Ungleichung in eine Gleichheit ändern: . Ich verstehe immer noch nicht, warum es dann fehlschlägt, aber vielleicht fehlt mir etwas. Ich habe nicht viel darüber nachgedacht. dichj=pj- -pich
Peter Shor
Wahrscheinlich fehlt mir hier etwas. Garantiert dies, dass alle ganzzahlige Werte annehmen? Man könnte p i von oben mit 1 binden , aber ich bin mir nicht sicher, ob das funktioniert oder nicht. Das Problem scheint zu sein, dass man, wenn dies gelöst werden kann, den Maximalschnitt durch Umkehren der Kantengewichte reduzieren könnte, was nicht möglich sein sollte, da der Maximalschnitt NP-hart ist. Allerdings könnte ich mich hier irren. pichpich
George
1
Ist st max-cut NP-hart für DAGs? Wenn das Diagramm keine DAG ist, können Sie diese Ungleichung nicht in eine Gleichheit ändern, da Sie die Ungleichung benötigen, wenn Zyklen vorhanden sind. Im Allgemeinen funktioniert die LP also nicht mit negativen Gewichten.
Peter Shor

Antworten:

10

Sie haben Ihr Problem in den Kommentaren noch weiter verfeinert. Genauer gesagt haben Sie eine DAG, bei der alle Kanten von der Quelle weg und in Richtung der Senke t fließen (dh alle Kanten befinden sich auf einem Pfad von s nach t ). Sie möchten den minimalen Schnitt zwischen zwei Teilen der DAG finden, wobei das erste Teil mit s und das zweite mit t verbunden ist . Für dieses Problem funktioniert eine Variation des Standardalgorithmus für die lineare Programmierung für MIN-CUT auch bei negativen Kantengewichten.ststst

Wir verwenden die gleiche Notation wie in Wikipedia . Die Kosten für die Kante ist , c i j . Wir setzen eine potentielle Funktion p i auf jeden Knoten und lassen d i j = p i - p j . Die LP ist m i n i m i z e(ich,j)cichjpichdichj=pich- -pj

michnichmichze (ich,j)E.cichjdichjsubject tÖ    dichj=pich- -pj  (ich,j)E.   dichj0           (ich,j)E.   ps=1   pt=0

Diese Gleichungen garantieren , dass , da jeder Knoten auf einige ist s - t Weg. In ähnlicher Weise nehmen die Potentiale auf jedem Weg von s nach t ab , da d i j = p i - p j nicht negativ ist . Wir müssen noch zeigen, dass es eine optimale Lösung für die LP mit allen p i entweder 0 oder 1 gibt . Dies folgt aus der Tatsache, dass der Wert für eine Lösung des obigen LP der erwartete Wert des Schnitts C w ist , wobei0pich1stdichj=pich- -pjstpich01C.w wird in [ 0 , 1 ] zufällig ausgewählt, und wobei der Schnitt C w erhalten wird, indem alle Eckpunkte i mit p iw in den ersten Satz von Eckpunkten und alle Eckpunkte mit p i < w in den zweiten Satz gesetzt werden.w[0,1]]C.wichpichwpich<w

Peter Shor
quelle
0pichleq1
@ George: Es ist das gleiche Argument, das zeigt, dass die reguläre Min-Cut-LP integrale Lösungen hat. Irgendwo online sollte es eine längere (und verständlichere) Erklärung geben.
Peter Shor
Ok, ich werde danach suchen. Nochmals vielen Dank für Ihre Hilfe!
George