Maximaler Schnitt

Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen, so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig.

Das Problem wird auf einem ungerichteten Graphen betrachtet. Gegeben ist neben dem Graphen ${\displaystyle G=(V,E)}$ eine Kantengewichtsfunktion ${\displaystyle w:E\rightarrow \mathbb {R} }$, die jeder Kante ein reelles Gewicht zuweist.

Gesucht ist eine Bipartition ${\displaystyle (S,T)}$ der Knotenmenge ${\displaystyle V}$, so dass das Gesamtgewicht ${\displaystyle \sum _{u\in S,v\in T}w(u,v)}$ aller Kanten ${\displaystyle \{u,v\}\in E}$, für die der eine Endknoten in der einen und der andere Endknoten in der anderen der beiden disjunkten Teilmengen ${\displaystyle S}$ und ${\displaystyle T}$ der Knotenmenge ${\displaystyle V}$ enthalten ist, also entweder ${\displaystyle u\in S}$ und ${\displaystyle v\in T}$ oder ${\displaystyle u\in T}$ und ${\displaystyle v\in S}$, maximal ist.

Für den Spezialfall, dass alle Kantengewichte gleich sind, die Kantengewichtsfunktion also konstant ist, kann das Problem auch wie folgt definiert werden:

• Gesucht ist eine Teilmenge ${\displaystyle S}$ von ${\displaystyle V}$, sodass die Anzahl der Kanten zwischen ${\displaystyle S}$ und der komplementären Teilmenge ${\displaystyle T=V\setminus S}$ möglichst groß ist.
• Gesucht ist ein bipartiter Teilgraph des Graphen mit maximaler Anzahl von Kanten.

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

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 ${\displaystyle \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 ${\displaystyle C_{1}\ldots C_{m}}$ mit jeweils dreien der Literale ${\displaystyle 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 ${\displaystyle 2n}$ Knoten, beschriftet mit ${\displaystyle 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 ${\displaystyle C_{i}=(a,b,c)}$ dann werden die Kanten ${\displaystyle (a,b)}$, ${\displaystyle (b,c)}$ und ${\displaystyle (a,c)}$ erstellt; bei einer Klausel ${\displaystyle C_{i}=(a,b,b)}$ also nur ${\displaystyle (a,b)}$ und nochmals ${\displaystyle (a,b)}$; und eine Klausel ${\displaystyle C_{i}=(a,a,a)}$ induziert gar keine Kanten.
   3. Zeichne so viele Kanten zwischen ${\displaystyle x_{i}}$ und ${\displaystyle {\bar {x_{i}}}}$, wie oft ${\displaystyle x_{i}}$ und ${\displaystyle {\bar {x_{i}}}}$ insgesamt zusammengerechnet in allen Klauseln auftreten.
   4. Sei ${\displaystyle X}$ die Menge der wahren Literale, um Not-All-Equal-3-SAT zu erfüllen. Dann hat im Graph der Schnitt ${\displaystyle (V,V\backslash X)}$ die Größe ${\displaystyle 5m}$: Zu ihm gehören alle ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 5m}$: Es ist sichergestellt, dass der Schnitt alle in 3 eingefügten ${\displaystyle 3m}$ Kanten umfasst, jedoch kann er nicht die aus 2 nötigen ${\displaystyle 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 ${\displaystyle 5m}$ hat, so muss dieser zunächst alle Kanten aus 3 enthalten (aufgrund der Summierung von ${\displaystyle x}$ und ${\displaystyle {\bar {x}}}$ ergäbe sich sonst kein Maximum). Wenn er nun noch weitere ${\displaystyle 2m}$ Kanten enthält, so müssen in der booleschen Formel genug widerspruchsfreie Klauseln für eine passende Belegung existiert haben.

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, terminiert dieser Vorgang tatsächlich irgendwann). Das Problem ist jedoch, dass die Laufzeit nur pseudopolynomiell in Abhängigkeit vom Gesamtgewicht ist.

Um tatsächlich polynomielle Laufzeit zu erreichen, werden nur Flips vorgenommen, die eine große Verbesserung des Gewichts bringen, genauer: das Verhältnis Gewicht${\displaystyle /|V|}$ mindestens um den Faktor ${\displaystyle (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.

• Zur NP-Vollständigkeit: Guan-Shieng Huang: Theory of Computation. (PDF; 404 kB). S. 7 ff.
• Zu den Approximationsalgorithmen: Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson International Edition. Pearson u. a., Boston MA u. a. 2006, ISBN 0-321-37291-3, S. 676 ff.