Transcript
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Theoretische Informatik 1 Vollständigkeit 2
David Kappel Institut für Grundlagen der Informationsverarbeitung Technische Universität Graz
12.06.2015
Zusammenfassung
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Übersicht
CLIQUE ist NP-Vollständig CLIQUE ist in NP CLIQUE ist NP-schwer HAMILTON-PATH ist NP-Vollständig HAMILTON-PATH ist in NP HAMILTON-PATH ist NP-schwer Zusammenfassung
Zusammenfassung
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
CLIQUE
Definition (CLIQUE) geg: ungerichteter Graph G = (V , E) mit m Knoten, k ∈ N CLIQUE = hG, k i G hat Clique der Größe k
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
NP-Vollständigkeit
Satz CLIQUE ist NP-Vollständig CLIQUE ∈ NP
∧
∀A ∈ NP : A ≤P CLIQUE
zu zeigen: • CLIQUE ∈ NP • CLIQUE ist NP-schwer • Beweis durch Reduktion 3SAT ≤P CLIQUE
Zusammenfassung
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
CLIQUE ∈ NP Algorithmus: • Erzeuge eine Liste von Zahlen p1 . . . pk • pi werden Nicht-deterministisch zwischen 1 und m erzeugt • Überprüfe ob Wiederholungen in der Liste vorkommen,
wenn ja verwerfe • Überprüfe ob Liste eine Clique ist, d.h. ob Kante (pi , pj ) für
jedes Paar existiert, wenn nein verwerfe • Ansonsten akzeptiere
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
CLIQUE ist NP-schwer Bewisidee: • Beweis durch Reduktion: 3SAT ≤P CLIQUE • d.h. zeige eine Konstruktion eines ungerichteten Graphen,
G = (V , E) mit der Eigenschaft: Es existiert eine Clique der Größe k in G, genau dann wenn 3-KNF Formel φ, mit k Klauseln, erfüllbar ist. • φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck ) • jedes Literal a, b und c ist von der Form xi oder ¬xi • x1 . . . xL sind die Variablen von φ
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Vorüberlegungen 3SAT (Beispiel):
Vorüberlegungen: • 3 KNF in L = 4 Variablen mit K = 5 Klauseln • Formel ist genau dann erfüllt wenn jede Klauseln erfüllt ist • Jede Klausel muss mindestens ein erfülltes Literal besitzen • Sich widersprechende Literale können nicht gleichzeitig
erfüllt sein
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
CLIQUE ist NP-schwer Vorüberlegungen: • φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck ) • φ ist genau dann erfüllt, wenn jede der k Klauseln erfüllt ist • Eine Klausel ist erfüllt, wenn mind. ein Literal erfüllt ist • Ist φ nicht erfüllt, enthält sie einen Widerspruch (z.B.: x1
und ¬x1 ) • Idee: jedes Literal wird durch einen Knoten im Graph
dargestellt • Wenn Literal erfüllt, dann soll es Teil der Clique sein
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Konstruktion des Graphen1 : • Der Graph hat 3 ∗ k Knoten,
entsprechend den Literalen von φ
Zusammenfassung
Veranschaulichung: φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck ) a1
b1
c1
• Die Knoten von G sind in k
Gruppen organisiert • Jede Gruppe besteht aus 3
a2
b2
1
c2
2
a3
b3
• Jedem Knoten wird ein Literal
aus der entsprechen Klausel zugeordnet 1
Siehe Sipser p. 278ff
ak
bk
c3 3
...
Knoten und entspricht einer Klausel
ck k
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Veranschaulichung: Konstruktion des Graphen1 :
φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck )
• Die Kanten von G verbinden
x1
x2
x3
alle Knoten außer:
Gruppe (Klausel)
x1
x2
2
x2
x1
Literalen (z.B.: x1 und ¬x1 ) ak
bk
ck k
Siehe Sipser p. 278ff
x3 3
...
• Knoten mit widersprechenden
1
a1= b1= c1= a2=
1
x1 x2 x3 x3
...
x3
• Knoten innerhalb einer
x=(x1 x2 x3 x4)
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
CLIQUE ist NP-schwer Beispiel:
φ = (x1 ∨ x1 ∨ x2 ) ∧ (¬x1 ∨ ¬x2 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 ∨ x2 )
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Beweis der Korrektheit Angenommen φ ist erfüllbar • Zumindest ein Literal ist wahr in jeder Klausel • Wenn mehr als ein Literal wahr ist wird zufällig eines
gewählt • → In jeder 3-er Gruppe wird ein Knoten gewählt • Zwischen jedem Knotenpaar existiert eine Kante, denn • ...alle Knoten sind von unterschiedlichen Gruppen • ...eine Erfüllende Variablenbelegung enthält keine
Widersprüche • → Daher enthält G eine k -Clique
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Beweis der Korrektheit Angenommen G enthält eine k -Clique • Da keine Kanten innerhalb der Gruppe, können nie 2
Knoten aus der gleichen Gruppe gewählt werden • Wahrheitswerte werden den Variablen von φ zugewiesen
indem die den gewählten Knoten entsprechenden Literale auf wahr gesetzt werden • Das ist immer möglich da widersprüchliche Zuweisungen
nicht mit einer Kante verbunden sind, daher nicht in der Clique • Diese Zuweisung ist erfüllend, da sich in jeder Klausel ein
erfüllendes Literal befindet • → Daher ist φ erfüllbar
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Beispiel
Zusammenfassung
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH Definition (HAMILTON-PATH) geg: gerichteter Graph G = (V , E), s, t ∈ V HAMILTON-PATH = hG, s, ti ∃ Hamilton-Pfad von s nach t in G Hamilton-Pfad: • Sei Anzahl der Knoten m • Permutation der Knoten p1 . . . pm heißt Hamilton-Pfad von
s nach t, wenn: • p1 = s und pm = t • Jedes Paar (pi , pi+1 ) ist eine Kante von G
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
NP-Vollständigkeit Satz HAMILTON-PATH ist NP-Vollständig, i.e.: HAMILTON-PATH ∈ NP ∧ ∀A ∈ NP : A ≤P HAMILTON-PATH zu zeigen: • HAMILTON-PATH ∈ NP • HAMILTON-PATH ist NP-schwer • Beweis durch Reduktion 3SAT ≤P HAMILTON-PATH
Zusammenfassung
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ∈ NP Algorithmus: • Erzeuge eine Liste von Zahlen p1 . . . pm • pi werden Nicht-deterministisch zwischen 1 und m erzeugt • Überprüfe ob Wiederholungen in der Liste vorkommen,
wenn ja verwerfe • Überprüfe ob Liste ein Hamilton-Pfad ist, d.h. ob Kante
(pi , pi+1 ) für jedes Paar existiert, wenn nein verwerfe • Ansonsten akzeptiere
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ist NP-schwer Bewisidee: • Beweis durch Reduktion: 3SAT ≤P HAMILTON-PATH • d.h. zeige eine Konstruktion eines gerichteten Graphen,
G = (V , E) mit der Eigenschaft: Es existiert eine Hamilton-Pfad, genau dann wenn 3-KNF Formel φ erfüllbar ist. • φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck ) • jedes Literal a, b und c ist von der Form xi oder ¬xi • x1 . . . xL sind die Variablen von φ
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ist NP-schwer Vorüberlegungen: • φ = (a1 ∨ b1 ∨ c1 ) ∧ (a2 ∨ b2 ∨ c2 ) ∧ . . . ∧ (ak ∨ bk ∨ ck ) • φ ist genau dann erfüllt, wenn jede der k Klauseln erfüllt ist • Eine Klausel ist erfüllt, wenn mind. ein Literal erfüllt ist • Idee: Jede Variable wird durch einen Diamanten-Förmigen
Teilgraph dargestellt (siehe Tafel, oder Sipser Seite 293) • Jede Klausel wird durch einen einzelnen Knoten dargestellt
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ist NP-schwer • L-mal Diamant-Struktur (pro
variable): 2 Eingänge, 2 Ausgänge • Kann nur in einer Richtung
durchwandert werden • Nicht-deterministische
Entscheidung (links = 1, rechts = 0) • Für jede Verwendung der
Variable, Abzweigung über Klausel-Knoten (k -mal) 1
siehe Sipser, Abb. 7.47 - 7.54
Veranschaulichung1 :
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ist NP-schwer Veranschaulichung1 : • Rechts-nach-links, falls Literal
negiert • Links-nach-rechts, sonst • Wenn Klausel-Knoten im
Graphen besucht wurde, dann erfüllt • Wenn alle Knoten besucht
wurden dann ist φ erfüllt
1
siehe Sipser, Abb. 7.47 - 7.54
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ist NP-schwer Beispiel:
φ = (x1 ∨ x2 ) ∧ (¬x1 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 ) s 1
0
0
1
1
0
x1
g2
g1
x2 1
0 t
g3
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Beweis der Korrektheit Angenommen φ ist erfüllbar • Wir zeigen die Existenz eines Hamilton-Pfades • Zunächst ignorieren wir die Klausel-Knoten • Jedes Diamanten-Modul wird von rechts nach links oder
von links nach rechts durchlaufen (wahr, oder falsch Zuweisung) • Jeder Klausel-Knoten kann erreicht werden, in einer
erfüllenden Belegung • → Daher enthält G einen Hamilton-Pfad
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Beweis der Korrektheit Angenommen G enthält einen Hamilton-Pfad • Wir zeigen das φ erfüllbar ist • Jeder Links-Rechts-Entscheidung in den Diamanten wird
die Variablenbelegung (wahr,falsch) zugeordnet • Diese Belegung erfüllt φ, denn • Jede Variable muss belegt sein, das sonst ein Knoten
übersprungen würde • Die Belegung enthält keine Widersprüche da sonst mind.
ein Klausel-Knoten nicht besucht werden könnte • → Daher ist φ erfüllbar
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
HAMILTON-PATH ≤L UHAMILTON-PATH Definition (UHAMILTON-PATH) geg: ungerichteter Graph G = (V , E), s, t ∈ V UHAMILTON-PATH = hG, s, ti ∃ Hamilton-pfad von s nach t in G Trick: 1 Knoten wird zu 3 Knoten
siehe z.B. Schöning, S. 166f oder Spiser, S. 295
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Pfad vs. Kreis
• Analog zu HAMILTON-PATH bzw. UHAMILTON-PATH gibt
es HAMILTON-CIRCLE bzw. UHAMILTON-CIRCLE oder oft einfach HAMILTON bzw. UHAMILTON • Zusätzliche Forderung (pm , p1 ) ∈ E (damit ist die Angabe
von s und t überflüssig) • Aus analogen Überlegungen folgt dass sowohl HAMILTON
als auch UHAMILTON NP-Vollständig sind siehe auch Schöning, S. 163-167 für einen alternativen Beweis
CLIQUE ist NP-Vollständig
HAMILTON-PATH ist NP-Vollständig
Zusammenfassung
Zusammenfassung • CLIQUE ist in NP • HAMILTON-PATH ist NP-Vollständig • Mehrere 1000 NP-Vollständige Probleme • Siehe Liste der NP-Vollständige Probleme http://en.wikipedia.org/wiki/List_of_NP-complete_problems
•
Vertex cover, Dominating set, Domatic partition, Graph coloring, Complete coloring, Monochromatic triangle, Feedback vertex, Feedback arc set, Partial feedback edge set, Minimum maximal independent set, Partition into triangles, Partition into isomorphic subgraphs, Partition into Hamiltonian subgraphs, Partition into forests, Partition into perfect matchings, Two-stage maximum weight stochastic matching, Clique covering problem, Berth allocation problem, Covering by complete bipartite subgraphs, Grundy number, Rank coloring, Treewidth, Clique, Independent set, Induced path, Balanced complete bipartite subgraph, Bipartite subgraph, Degree-bounded connected subgraph, Planar subgraph, Edge-subgraph, Transitive subgraph, Uniconnected subgraph, Minimum k-connected subgraph, Cubic subgraph, Minimum equivalent digraph, Hamiltonian completion, Interval graph completion, ...
