Vollständigkeit 2 - Institut für Grundlagen der Informationsverarbeitung

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 iG 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, ...