Polynomielle Reduktionen zwischen NP-Problemen
Lesen anpassen
Nach dieser Lektion kannst du
eine Instanz von 3-SAT in einen Kompatibilitätsgraphen mit der richtigen Zielgröße übersetzen,
die Äquivalenz von erfüllender Belegung und Clique in beiden Richtungen beweisen,
Graphkomplement und Mengenkomplement unterscheiden,
aus einer Schwereübertragung und einem Verifizierer einen vollständigen NP-Vollständigkeitsbeweis zusammensetzen.
Vorausgesetzt: NP-Vollständigkeit und der Satz von Cook–Levin, Bäume und Graphen
Eine Formel verlangt, dass in jeder Klausel mindestens ein Literal wahr ist. Statt alle Wahrheitswerte sofort festzulegen, können wir zunächst in jeder Klausel einen möglichen Zeugen auswählen. Die gewählten Zeugen müssen miteinander vereinbar sein: Man darf nicht gleichzeitig x und ¬x als wahr verlangen.
Das klingt nach einem Graphproblem. Jedes Literalvorkommen wird zu einem Knoten. Eine Kante soll heißen: Diese beiden Vorkommen dürfen gemeinsam gewählt werden. Eine große vollständig verbundene Knotenauswahl kann dann eine erfüllende Belegung vertreten. Wir bauen diesen Gedanken präzise aus und übertragen die Schwere danach auf zwei weitere Graphprobleme.
Die drei Graphentscheidungsprobleme
Alle Graphen dieser Lektion sind endlich, ungerichtet, ohne Schleifen und ohne Mehrfachkanten. Eine Clique ist eine Knotenmenge, in der jedes Paar verschiedener Knoten benachbart ist. CLIQUE fragt zu G und einer nichtnegativen ganzen Zahl k nach einer Clique mit mindestens k Knoten. Eine größere Clique enthält auch eine mit genau k Knoten.
Eine unabhängige Menge enthält dagegen keine Kante zwischen ihren Knoten. INDEPENDENT-SET fragt nach mindestens k Knoten dieser Art. Eine Knotenüberdeckung oder ein Vertex Cover C enthält mindestens einen Endpunkt jeder Kante. VERTEX-COVER fragt nach einer solchen Menge mit höchstens k Knoten. Isolierte Knoten müssen nicht überdeckt werden. Bei den ersten beiden Problemen ist eine große, beim dritten eine kleine Menge gewünscht.
Eine Formel mit drei kurzen Klauseln
Eine Formel mit drei kurzen Klauseln
Wir verwenden 3-SAT mit höchstens drei Literalen pro Klausel. Betrachte die Formel mit , und . Die Belegung x=y=1 erfüllt alle drei Klauseln. Als wahre Zeugen können wir x aus der ersten, y aus der zweiten und x aus der dritten Klausel auswählen.
Das sind drei verschiedene Vorkommen, obwohl x zweimal denselben Variablennamen hat. Die Knoten müssen diese Vorkommen getrennt darstellen, weil sie zu verschiedenen Klauseln gehören. Ein Zusammenlegen gleicher Variablennamen würde die Übersetzung verändern.
Von 3-SAT zu CLIQUE
Von 3-SAT zu CLIQUE
Sei φ eine 3-KNF mit m Klauseln. Für die eigentliche Konstruktion nehmen wir an, dass jede Klausel mindestens ein Literal enthält. Die Sonderfälle werden anschließend festgelegt.
Lege für jedes Literalvorkommen einen eigenen Knoten an. Die Knoten derselben Klausel bilden eine Gruppe, innerhalb derer es keine Kanten gibt.
Drei Klauseln, sechs Vorkommen, eine passende Clique
Gewählte Clique: x aus C1, y aus C2, x aus C3.
Jeder Kreis ist ein Literalvorkommen. Die hervorgehobenen Knoten und Kanten bilden die Clique zur Belegung x=y=1. Die übrigen Kanten zeigen weitere erlaubte Paare; nicht jede erlaubte Paarwahl lässt sich zu einer vollständigen Clique ergänzen.
Die Formel ist erfüllbar genau dann, wenn eine m-Clique existiert
Für die beschriebene Konstruktion gilt genau dann, wenn .
Hinrichtung: Wähle zu einer erfüllenden Belegung aus jeder Klausel ein wahres Literal. Die m ausgewählten Vorkommen stammen aus verschiedenen Gruppen. Zwei von ihnen können nicht x und ¬x verlangen, weil unter einer Belegung nicht beide wahr sind. Also sind alle Paare verbunden und bilden eine Clique.
Rückrichtung: Eine Clique kann aus jeder Gruppe höchstens einen Knoten nehmen. Hat sie mindestens m Knoten, enthält sie daher genau einen aus jeder der m Gruppen. Die gewählten Literale enthalten kein widersprüchliches Paar x,¬x. Setze jede positiv gewählte Variable auf eins und jede negativ gewählte auf null. Noch nicht gewählte Variablen dürfen beliebig belegt werden. Jede Klausel besitzt ihren gewählten wahren Zeugen und ist erfüllt.
Dürfen zwei Vorkommen desselben positiven Literals x aus verschiedenen Klauseln verbunden sein?
Graphkomplement
Das Graphkomplement besitzt dieselben Knoten wie G. Zwei verschiedene Knoten sind in genau dann verbunden, wenn sie in G nicht verbunden sind. Schleifen werden dabei weiterhin nicht hinzugefügt.
Eine k-Clique in G ist daher genau eine unabhängige Menge mit k Knoten in . Die Knotenauswahl bleibt dieselbe, nur die Kantenrelation wird umgekehrt. Das Komplement lässt sich durch Prüfen aller Knotenpaare polynomiell erzeugen.
Eine unabhängige Menge entspricht der Überdeckung ihres Mengenkomplements
Für eine Knotenmenge I in einem Graphen H ist I unabhängig genau dann, wenn eine Knotenüberdeckung ist. Das ist ein Mengenkomplement im selben Graphen und kein weiterer Wechsel der Kanten.
Ist I unabhängig, hat keine Kante beide Endpunkte in I. Jede Kante besitzt daher mindestens einen Endpunkt außerhalb von I, also in C. Umgekehrt würde eine Kante mit beiden Endpunkten in I keinen Endpunkt in C besitzen und der Überdeckung widersprechen. Für die Größen gilt . Eine unabhängige Menge mit mindestens k Knoten entspricht somit einer Überdeckung mit höchstens Knoten.
Die ganze Kette am Sechsknotengraphen
Die ganze Kette am Sechsknotengraphen
Der Beispielgraph G hat sechs Knoten und acht Kanten. Die drei gewählten Vorkommen bilden eine 3-Clique. Im Graphkomplement sind genau diese drei Knoten unabhängig. Die übrigen drei Knoten bilden deshalb eine Knotenüberdeckung von .
Wichtig sind beide Wechsel: erst G zum Graphkomplement, dann die gewählte Knotenmenge zu ihrem Mengenkomplement. Die Konstruktion behauptet nicht, dass die drei übrigen Knoten eine Überdeckung im ursprünglichen G bilden. Die vollständige Zielinstanz lautet hier .
Den NP-Vollständigkeitsbeweis fertigstellen
Den NP-Vollständigkeitsbeweis fertigstellen
Die Reduktionskette liefert zunächst Schwere. Die Zugehörigkeit der drei Graphprobleme zu NP muss zusätzlich begründet werden.
Für CLIQUE gib als Zertifikat k verschiedene gültige Knoten an und prüfe alle Paare auf eine Kante. Bei k>|V| wird sofort verworfen.
Die Reduktion überträgt automatisch alle Optimierungs- und Näherungseigenschaften
Die Reduktion überträgt automatisch alle Optimierungs- und Näherungseigenschaften
Eine Ja-Nein-Äquivalenz wird manchmal so gelesen, als erhalte dieselbe Übersetzung auch Lösungswerte, optimale Lösungen und Näherungsfaktoren unverändert.
Eine many-one-Reduktion erhält zunächst nur die Entscheidungsantwort. In dieser Kette können die ausgewählten Mengen ausdrücklich zurückübersetzt werden, aber die Werte wechseln etwa von k zu |V|−k. Ein multiplikativer Näherungsfaktor bleibt bei einer solchen Subtraktion nicht automatisch erhalten. Dafür bräuchte man eine gesonderte Analyse. Auch die praktische Laufzeit kann durch größere Zielinstanzen steigen, obwohl die Übersetzung polynomiell ist.
Zusammenfassung
Die 3-SAT-Konstruktion verwendet einen Knoten pro Literalvorkommen und eine Gruppe pro Klausel.
Kanten verbinden verschiedene Gruppen mit vereinbaren Literalen. Zielgröße ist die Anzahl der Klauseln.
Erfüllbarkeit und passende Clique werden in beiden Richtungen bewiesen.
Eine Clique in G wird im Graphkomplement zu einer unabhängigen Menge derselben Größe.
Das Mengenkomplement einer unabhängigen Menge ist im selben Graphen eine Knotenüberdeckung; die Grenze wechselt von k zu |V|−k.
Polynomielle Ausgabegröße, totale Behandlung der Sonderfälle und NP-Verifizierer vervollständigen den Beweis.
Näherungsgarantien folgen nicht automatisch aus einer Ja-Nein-Reduktion.
Übungen
Wann erhält ein Knotenpaar im 3-SAT-Kompatibilitätsgraphen eine Kante?
Die Beispielformel besteht aus drei Klauseln mit je zwei Literalen. Wie viele Knoten erhält der Graph vor irgendeiner Vereinfachung?
Wie viele Kanten besitzt der Kompatibilitätsgraph der angegebenen drei Beispielklauseln?
Eine CLIQUE-Instanz hat neun Knoten und Zielgröße drei. Welches Überdeckungsbudget entsteht nach Graphkomplement und Übersetzung der unabhängigen Menge?
Welche Aussage ist ohne weitere Annahmen richtig?
Begründe die Rückrichtung von einer m-Clique zur erfüllenden Belegung. Warum reicht paarweise Verträglichkeit hier aus?
Warum darf man alle Knoten mit gleichem Literallabel nicht einfach zusammenlegen, auch wenn dadurch der Graph kleiner wird?
Die Schwere von VERTEX-COVER ist durch die Kette gezeigt. Ergänze den noch fehlenden Teil eines NP-Vollständigkeitsbeweises.