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

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).

algorithms complexity-theory graph-theory weighted-graphs George
quelle

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

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.

d_{i j} = p_{j} - p_{i}

$d_{ij} = p_j - p_i$

Peter Shor

Wahrscheinlich fehlt mir hier etwas. Garantiert dies, dass alle

ganzzahlige Werte annehmen? Man könnte

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.

p_{i}

$p_i$

p_{i}

$p_i$

George

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:

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 fließen (dh alle Kanten befinden sich auf einem Pfad von nach ). Sie möchten den minimalen Schnitt zwischen zwei Teilen der DAG finden, wobei das erste Teil mit und das zweite mit . Für dieses Problem funktioniert eine Variation des Standardalgorithmus für die lineare Programmierung für MIN-CUT auch bei negativen Kantengewichten. $s$ $t$ $s$ $t$ $s$ $t$

Wir verwenden die gleiche Notation wie in Wikipedia . Die Kosten für die Kante ist , . Wir setzen eine potentielle Funktion auf jeden Knoten und lassen . Die LP ist $(i,j)$ $c_{ij}$ $p_i$ $d_{ij} = p_i - p_j$

\begin{aligned} m ich n ich m ich z e & \sum_{(ich, j) \in E.} c_{ich j} d_{ich j} \\ s u b j e c t t Ö & d_{ich j} = p_{ich} - - p_{j} \forall (ich, j) \in E. \\ d_{ich j} \geq 0 \forall (ich, j) \in E. \\ p_{s} = 1 \\ p_{t} = 0 \end{aligned}

$\begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\ \mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij} \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \ p_s\, = 1 \\ & \ \ \ p_t \, = 0 \end{align*}$

Diese Gleichungen garantieren , dass , da jeder Knoten auf einige ist - Weg. In ähnlicher Weise nehmen die Potentiale auf jedem Weg von nach , da nicht negativ ist . Wir müssen noch zeigen, dass es eine optimale Lösung für die LP mit allen entweder oder . Dies folgt aus der Tatsache, dass der Wert für eine Lösung des obigen LP der erwartete Wert des Schnitts , wobei $0 \leq p_i \leq 1$ $s$ $t$ $d_{ij} = p_i - p_j$ $s$ $t$ $p_i$ $0$ $1$ $C_w$ wird in zufällig ausgewählt, und wobei der Schnitt erhalten wird, indem alle Eckpunkte mit in den ersten Satz von Eckpunkten und alle Eckpunkte mit in den zweiten Satz gesetzt werden. $w$ $[0,1]$ $C_w$ $i$ $p_i\geq w$ $p_i < w$

Peter Shor
quelle

0 \leq p_{i} l e q 1

$0 \leq p_i leq 1$

@ 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