Maximaler Schnitt

Der maximale Schnitt eines Graphen ist eine Zuordnung seiner Knotenmenge V in zwei Partitionen (S,T), so dass das Gesamtgewicht der zwischen den beiden Partitionen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig.

Formale Schreibweise

Das Problem wird auf einem ungerichteten Graphen betrachtet. Gegeben ist neben dem Graph G = (V,E) eine Bewertungsfunktion $w: E \rightarrow \mathbb{Z}^+$, also die Kantengewichte.

Gesucht ist eine Partition (S,T) so dass $\sum_{u \in S, v\in T} w(u,v)$ maximal wird.

NP-Vollständigkeit

Entscheidungsproblem

Das entsprechende Entscheidungsproblem fragt für eine Eingabe (G,w) und b > 0: Gibt es einen Schnitt, dessen Wert größer als b ist?

Beweis

1. Das Problem liegt in NP, da eine - wie auch immer gefundene - Lösung ("Zeuge") in Polynomialzeit verifiziert werden kann (es muss nur der Wert des gegebenen Schnitts berechnet werden, und geprüft werden, ob er $\geq b$ ist).
2. Das Problem ist auch NP-vollständig, denn es ist eine Reduktion von Not-All-Equal-3-SAT möglich: Die Eingabe besteht - wie beim normalen 3-SAT - aus einer Klauselmenge $C_1\ldots C_m$ mit jeweils dreien der Literale $x_1 \ldots x_n$. Not-All-Equal-3-SAT fragt nun: gibt es eine Belegung, so dass jede Klausel mindestens ein wahres und ein falsches Literal beinhaltet?
   Als Eingabe für den maximalen Schnitt wird nun ein Graph wie folgt konstruiert und verwendet:
   1. Er hat 2n Knoten, beschriftet mit $x_1 \ldots x_n, \bar{x_1} \ldots \bar{x_n}$.
   2. Aus jeder Klausel werden die sich nicht ausschließenden Belegungen der Literale verbunden: Sei C_i = (a,b,c) dann werden die Kanten (a,b), (b,c) und (a,c) erstellt; bei einer Klausel C_i = (a,b,b) also nur (a,b) und nochmals (a,b); und eine Klausel C_i = (a,a,a) induziert gar keine Kanten.
   3. Zeichne so viele Kanten zwischen x_i und $\bar{x_i}$, wie oft x_i und $\bar{x_i}$ insgesamt zusammengerechnet in allen Klauseln auftreten.
   4. Sei X die Menge der wahren Literale, um Not-All-Equal-3-SAT zu erfüllen. Dann hat im Graph der Schnitt $(V, V \backslash X)$ die Größe 5m: Zu ihm gehören alle 3m Kanten, die in Schritt 3 hinzugefügt wurden (da eine Variable nur true oder false, aber nicht beides sein kann). Außerdem gehören mindestens 2m Kanten aus Schritt 2 dazu, weil von den sich nicht ausschließenden Literalen einer jeden Klausel mindestens einer true und der andere false sein muss.
   5. Existiert keine erfüllende Belegung für Not-All-Equal-3-SAT, so existiert auch kein Schnitt der Größe 5m: Es ist sichergestellt, dass der Schnitt alle in 3 eingefügten 3m Kanten umfasst, jedoch kann er nicht die aus 2 nötigen 2m Kanten umfassen, da es in der booleschen Formel nicht ausreichend nicht widersprüchliche Literale in den einzelnen Klauseln gab. Alternativ: Wenn der Graph einen Schnitt der Größe 5m hat, so muss dieser zunächst alle Kanten aus 3 enthalten (aufgrund der Summierung von x und $\bar{x}$ ergäbe sich sonst kein Maximum). Wenn er nun noch weitere 2m Kanten enthält, so müssen in der booleschen Formel genug widerspruchsfreie Klauseln für eine passende Belegung existiert haben.

Approximationsalgorithmen

2-Approximation

Die Partitionierung des Graphen wird durch den Status des Knotens (an/aus) festgelegt. Es wird nun versucht, den Gesamtwert der "guten" Kanten zu maximieren; das sind per Definition alle Kanten zwischen den Partitionen. Eine "Flip"-Operation schiebt dabei einen Knoten von einer Partition in die andere (schaltet ihn an oder aus). Es wird durch Aneinanderreihen von Flips ein lokales Maximum erreicht, indem solange zufällig Flips durchgeführt werden, wie dadurch der Gesamtwert verbessert wird (da der Gesamtwert beschränkt ist, und er mit jeder Operation steigt, termiert dieser Vorgang tatsächlich irgendwann). Das Problem ist jedoch, dass die Laufzeit nur pseudopolynomiell in Abhängigkeit des Gesamtgewichts ist.

(2+$\epsilon$)-Approximation

Um tatsächlich polynomielle Laufzeit zu erreichen, werden nur Flips vorgenommen, die eine große Verbesserung des Gewichts bringen, genauer: das Verhältnis Gewicht / | V | mindestens um den Faktor $(1+\epsilon)$ erhöhen. Dadurch wird bei einer linearen Anzahl von Flips das Gewicht vervielfacht, wodurch das Maximalgewicht in logarithmisch vielen Schritten erreicht werden kann; die Lösung wird allerdings etwas ungenauer, da selbst wenn noch eine kleine Verbesserung möglich wäre, diese nicht mehr vorgenommen wird.

Literatur

• Zur NP-Vollständigkeit: Guan-Shieng Huang: Theory of Computation (PDF). Seite 7ff.
• Zu den Approximationsalgorithmen: Jon Kleinberg, Éva Tardos: Algorithm Design. Pearson International Edition, 2006. ISBN 0-321-37291-3. Seiten 676ff.