Maximaler Schnitt

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Formale Schreibweise[Bearbeiten | Quelltext bearbeiten]

Das Problem wird auf einem ungerichteten Graphen betrachtet. Gegeben ist neben dem Graphen eine Bewertungsfunktion , die jeder Kante ein Gewicht zuweist.

Gesucht ist eine Partition so, dass maximal wird.

NP-Vollständigkeit[Bearbeiten | Quelltext bearbeiten]

Entscheidungsproblem[Bearbeiten | Quelltext bearbeiten]

Das entsprechende Entscheidungsproblem fragt für eine Eingabe und : Gibt es einen Schnitt, dessen Wert größer als ist?

Beweis[Bearbeiten | Quelltext bearbeiten]

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

Approximationsalgorithmen[Bearbeiten | Quelltext bearbeiten]

2-Approximation[Bearbeiten | Quelltext bearbeiten]

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.

(2+ε)-Approximation[Bearbeiten | Quelltext bearbeiten]

Um tatsächlich polynomielle Laufzeit zu erreichen, werden nur Flips vorgenommen, die eine große Verbesserung des Gewichts bringen, genauer: das Verhältnis Gewicht mindestens um den Faktor 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[Bearbeiten | Quelltext bearbeiten]