Lektion 4.3

Polynomielle Reduktionen zwischen NP-Problemen

55 min Lesezeit
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.

Definition

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.

Beispiel

Eine Formel mit drei kurzen Klauseln

Wir verwenden 3-SAT mit höchstens drei Literalen pro Klausel. Betrachte die Formel mit C1=(x∨y)C_1=(x\lor y), C2=(¬x∨y)C_2=(\neg x\lor y) und C3=(x∨¬y)C_3=(x\lor\neg y). 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.

φ=(x∨y)∧(¬x∨y)∧(x∨¬y)\varphi=(x\lor y)\land(\neg x\lor y)\land(x\lor\neg y)
Schritt für Schritt

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.

  1. Lege für jedes Literalvorkommen einen eigenen Knoten an. Die Knoten derselben Klausel bilden eine Gruppe, innerhalb derer es keine Kanten gibt.

Schritt 1 von 3

Drei Klauseln, sechs Vorkommen, eine passende Clique

C1C2C3xy¬xyx¬y

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.

Satz

Die Formel ist erfüllbar genau dann, wenn eine m-Clique existiert

Für die beschriebene Konstruktion gilt φ∈3SAT\varphi\in\mathrm{3SAT} genau dann, wenn ⟨Gφ,m⟩∈CLIQUE\langle G_\varphi,m\rangle\in\mathrm{CLIQUE}.

Kurz geprüft

Dürfen zwei Vorkommen desselben positiven Literals x aus verschiedenen Klauseln verbunden sein?

Definition

Graphkomplement

Das Graphkomplement G‾\overline G besitzt dieselben Knoten wie G. Zwei verschiedene Knoten sind in G‾\overline G 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 G‾\overline G. Die Knotenauswahl bleibt dieselbe, nur die Kantenrelation wird umgekehrt. Das Komplement lässt sich durch Prüfen aller Knotenpaare polynomiell erzeugen.

⟨G,k⟩∈CLIQUE  ⟺  ⟨G‾,k⟩∈INDEPENDENT-SET\langle G,k\rangle\in\mathrm{CLIQUE}\iff\langle\overline G,k\rangle\in\mathrm{INDEPENDENT\text{-}SET}
Satz

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 C=V(H)∖IC=V(H)\setminus I eine Knotenüberdeckung ist. Das ist ein Mengenkomplement im selben Graphen und kein weiterer Wechsel der Kanten.

Beispiel

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 G‾\overline G sind genau diese drei Knoten unabhängig. Die übrigen drei Knoten bilden deshalb eine Knotenüberdeckung von G‾\overline G.

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 (G‾,3)(\overline G,3).

3SAT≤pCLIQUE≤pINDEPENDENT-SET≤pVERTEX-COVER\mathrm{3SAT}\le_p\mathrm{CLIQUE}\le_p\mathrm{INDEPENDENT\text{-}SET}\le_p\mathrm{VERTEX\text{-}COVER}
Schritt für Schritt

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.

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

Schritt 1 von 4
Häufige Fehler

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.

Richtig ist

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

Aufgabe 1Multiple Choice

Wann erhält ein Knotenpaar im 3-SAT-Kompatibilitätsgraphen eine Kante?

Aufgabe 2Numerisch

Die Beispielformel besteht aus drei Klauseln mit je zwei Literalen. Wie viele Knoten erhält der Graph vor irgendeiner Vereinfachung?

Aufgabe 3Numerisch

Wie viele Kanten besitzt der Kompatibilitätsgraph der angegebenen drei Beispielklauseln?

Aufgabe 4Numerisch

Eine CLIQUE-Instanz hat neun Knoten und Zielgröße drei. Welches Überdeckungsbudget entsteht nach Graphkomplement und Übersetzung der unabhängigen Menge?

Aufgabe 5Multiple Choice

Welche Aussage ist ohne weitere Annahmen richtig?

Aufgabe 6Freitext

Begründe die Rückrichtung von einer m-Clique zur erfüllenden Belegung. Warum reicht paarweise Verträglichkeit hier aus?

Aufgabe 7Freitext

Warum darf man alle Knoten mit gleichem Literallabel nicht einfach zusammenlegen, auch wenn dadurch der Graph kleiner wird?

Aufgabe 8Freitext

Die Schwere von VERTEX-COVER ist durch die Kette gezeigt. Ergänze den noch fehlenden Teil eines NP-Vollständigkeitsbeweises.