3-SAT - Stabile Menge < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:24 Di 28.02.2006 | | Autor: | Tyr7 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Zusammen,
es geht diesmal um NP-Vollständigkeit und wie man anhand des 3-SAT Problems, das ja NP-vollständig ist, zeigen kann, dass stabile Menge eines Graphen auch NP-vollständig ist.
Im grunde ist mit die Logik dahinter klar, aber die Vorgehenweise in diesem Fall erscheint mir etwas unschlüssig. Dazu mal ein Beispiel:
f = [mm] (\neg [/mm] x1 [mm] \vee [/mm] x2 [mm] \vee [/mm] x3) [mm] \wedge [/mm] (x2 [mm] \vee \neg [/mm] x3 [mm] \vee [/mm] x4) [mm] \wedge [/mm] (x1 [mm] \vee \neg [/mm] x2 [mm] \vee [/mm] x4)
Dazu bastele ich einen Graphen, wo es soviele Knoten gibt wie Literale in f (also 9) und verbinde die Knoten in einer Klausel, so dass 3 Dreiecke entstehen. Dann verbinde ich die Knoten aus verschiedenen Dreiecken, wenn die Literale komplementaer sind. Also dazu zählen:
Klausel 1 mit Klausel 2 : x3
Klausel 2 mit Klausel 3 : x2
Klausel 1 mit Klausel 3 : x2, x1
Somit habe ich nur 2 freie Knoten x4 in Klausel 2 und x4 in Klausel 3. Nach der Definition (oder stimmt das jetzt nicht?) ist f erfüllbar, wenn die stabile Menge gleich der Anzahl der Klausel ist. In diesem Fall ist die stabile Menge bei mir 2, die Anzahl der Klausel aber 3, so dass f nicht erfüllbar sein dürfte.
Aber mit ein bisschen experimentieren komme ich doch auf eine Lösung, z.B: x1 = falsch und x4 = wahr.
Das meine ich mit unschlüssig :)
Oder sollte ich das so verstehen, dass wenn ich stabile Menge = Klauselanzahl habe, so ist f AUF JEDENFALL erfüllbar, sonst muss ich ja experimentieren, was mal klappen kann, mal nicht?
Vielen Dank und viele Grüße
Tyr
|
|
| |
|
Hallo und guten Morgen,
bei derlei Fragen bin ich von Hause aus geradezu verpflichtet zu antworten.
Ich moechte vorschlagen, von 3SAT nicht auf Stable Set, sondern auf Clique zu reduzieren.
(1) Stable Set versus Vertex Cover versus Clique
--------------------------------------
Sei G=(V,E) ein Graph, also mit endlicher Knotenmenge V und Kantenmenge
[mm] E\subseteq P_2(V):=\{\{u,v\}|\: u,v\in V,u\neq v\}.
[/mm]
Ein Vertex Cover ist eine Teilmenge [mm] U\subseteq [/mm] V der Knotenmenge von G, so dass
jede Kante von G mindestens einen Knoten in U hat (d.h. [mm] E\cap P_2(V\setminus U)=\emptyset).
[/mm]
Ein Stable Set (Independent Set, Stabile Menge, Unabhaengige Knotenmenge) ist eine Teilmenge [mm] W\subseteq [/mm] V
von V, so dass keine Kanten ganz innerhalb von W verlaufen, d.h. [mm] E\cap P_2(W)=\emptyset.
[/mm]
Eine Clique in G ist eine Teilmenge [mm] K\subseteq [/mm] V der Knotenmenge V, so dass K einen vollstaendigen Teilgraphen
induziert, d.h. je zwei Knoten von K sind durch eine Kante in G verbunden: [mm] P_2(K)\subseteq [/mm] E.
Definieren wir die zugehoerigen Entscheidungsprobleme in NP:
(a) Vertex Cover
Gegeben: Graph G=(V,E), natuerliche Zahl k (oE [mm] k\in \{1,\ldots , |V|\})
[/mm]
Frage: Gibt es ein Vertex Cover U in G der Groesse [mm] |U|\leq [/mm] k ?
(b) Stable Set
Gegeben: Graph G=(V,E), natuerliche Zahl k
Frage: Gibt es Stable Set W in G der Groesse [mm] |W|\geq [/mm] k ?
(c) Clique
gegeben: Graph G=(V,E), natuerliche Zahl k
Frage: Gibt es eine Clique K in G der Groesse [mm] |K|\geq [/mm] k ?
Reduktion von Stable Set auf Vertex Cover: [mm] (G,k)\mapsto [/mm] (G,|V|-k)
Reduktion von Vertex Cover auf Stable Set: [mm] (G,k)\mapsto [/mm] (G,|V|-k)
Reduktion von Stable Set auf Clique: [mm] (G,k)\mapsto (\overline{G},k)
[/mm]
wobei [mm] \overline{G}:= (V,P_2(V)\setminus [/mm] E) der Komplementgraph von G ist (mache Knaten zu Nicht-Kanten und Nicht-Kanten zu Kanten).
Grund fuer die Korrektheit der Reduktionen: Eine Menge [mm] U\subseteq [/mm] V ist Vertex Cover genau dann, wenn
[mm] V\setminus [/mm] U ein Stable Set ist - aequivalent: [mm] V\setminus [/mm] U Clique im Komplementgraph
[mm] \overline{G}. [/mm]
(2) Reduktion von 3SAT auf Clique
---------------------------------
Gegeben: 3SAT-Formel [mm] f=C_1\wedge\ldots \wedge C_m
[/mm]
mit Variablenmenge [mm] Var(f)=\{x_1,\ldots , x_n\}, [/mm] die [mm] C_i [/mm] sind die Klauseln.
Wir nehmen zu jeder Klausel [mm] C_i [/mm] und jedem Literal [mm] l\in\{x_1,\ldots , x_n, \neg x_1,\ldots , \neg x_n\}, [/mm] das in [mm] C_i [/mm] vorkommt,
einen Knoten (i,l).
V sei also die Menge aller dieser Knoten:
[mm] V=\bigcup_{i=1}^m\{(i,l)\: |\: Literal\: l\: kommt\: in\: Klausel\: C_i\: vor\}
[/mm]
Kanten werden nur zwischen Knoten existieren, die verschiedenen Klauseln entsprechen, und zwar dann, wenn die
beiden Literale einander nicht widersprechen, d.h. simultan auf 1 gesetzt werden koennen, d.h. das eine nicht Negation des anderen ist:
[mm] E=\{\: \{(i,l),(j,l')\}\:\: |\:\: 1\leq i
Sei G=(V,E), die Reduktion lautet:
[mm] f\mapsto [/mm] (G,m)
Korrektheit: Wir muessen argumentieren, dass G eine Clique der Groesse m hat genau dann, wenn f erfuellbar ist.
Beweis: Kanten existieren nur zw. vertraeglichen Literalen versch. Klauseln, d.h. eine Clique, die Knoten aus allen Klauseln enthaelt, erlaubt es
ja genau, die Klauseln simultan zu erfuellen. Klar ?
Ich find diese Reduktion am anschaulichsten.
Deine Reduktion auf Stable Set beschreibt gerade die Hintereinanderschaltung von Reduktion von 3SAT auf Clique und dann noch Bilden des Komplementgraphen,
aber ich find diese Vertraeglichkeitskanten anschaulicher als Unvertraeglichkeitskanten in [mm] \overline{G}.
[/mm]
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:48 Mi 01.03.2006 | | Autor: | Tyr7 |
Hallo Mathias,
erstmal danke für Deine ausführliche Beschreibung. Ist schon faszinierend, wie die Zusammenhänge zwischen den drei Mengen aussehen :)
Aber ich hätte da noch die eine Frage...
> Beweis: Kanten existieren nur zw. vertraeglichen Literalen
> versch. Klauseln, d.h. eine Clique, die Knoten aus allen
> Klauseln enthaelt, erlaubt es
> ja genau, die Klauseln simultan zu erfuellen. Klar ?
>
> Ich find diese Reduktion am anschaulichsten.
Ja, ist klar. Wenn eine Clique mit drei Knoten in den drei Klausel vorkommt, so heisst es dass dieser eine Literal für die Erfüllung der Funktion sorgen kann.
Aber was ist, wenn ich so eine Clique nicht habe? Das heisst doch nicht, dass die Funktion nicht erfüllbar ist. Habe das bei dem Beispiel von oben nochmal nachgerechnet und bekomme das gleiche Ergebnis. Es gibt keine Clique mit Größe 3 (habe ja auch keine Stabile Menge mit Größe 3 bekommen) aber die Funktion ist dennoch erfüllbar. Es gibt ja 2 Cliquen von Größe jeweils 2. Damit kann ich die Funktion erfüllen.
Du schreibst ja:
> Korrektheit: Wir muessen argumentieren, dass G eine Clique der Groesse m hat genau dann, wenn f erfuellbar ist.
Und jetzt: f ist erfuellbar aber keine Clique der Größe m... ???
Für mich sieht das wie eine Einbahnstrasse aus: wenn eine Clique existiert, dann ist f erfüllbar. "->"
Im Grunde besteht mein Problem in dem Beweis der anderen Richtung "<-". Mit der Richtung "->" bin ich einverstanden, aber zurück nicht...
Viele Grüße
Tyr
|
|
|
| |
|
Hallo Tyr,
vermutlich hast Du die Reduktion auf Stable Set mit der auf Clique verwechselt.
Betrachten wir Dein f= [mm] (\neg x_1\vee x_2\vee x_3)\wedge (x_2\vee \neg x_3\vee x_4)\wedge (x_1\vee \neg x_2\vee x_4).
[/mm]
Beschreiben wir die Reduktionen auf Stable Set (Notation fuer den Moment: [mm] f\mapsto (G_{f,S},3)) [/mm] und auf Clique (Notation fuer den Moment: [mm] f\mapsto (G_{f,C},3)).
[/mm]
Es gilt [mm] G_{f,S}=(V,E_{f,S})\:\: G_{f,C}=(V,E_{f,C})
[/mm]
mit
[mm] V=\{ (\neg x_1,1),(x_2,1),(x_3,1),\:\: (x_2,2), (\neg x_3,2),(x_4,2),\:\: (x_1,3), (\neg x_2,3), (x_4,3)\},
[/mm]
um Schreibarbeit zu sparen, notiere ich die Knoten etwas kompakter:
[mm] V=\{ (1,1),(2,1),(3,1),\:\:\: (2,2),(3,2),(4,2),\:\:\: (1,3), (2,3), (4,3)\}
[/mm]
Dann ist
[mm] E_{f,C}=\{\: \{(1,1,),(2,2)\},\: \{(1,1),(3,2),\},\: \{(1,1),(4,2)\}, \ldots\ldots\} [/mm] (ist echt zuviel Schreibarbeit).
Jedenfalls bilden die Knoten
(1,1), (2,2), (4,3) eine Clique in [mm] G_{f,C} [/mm] und ein Stable Set in [mm] G_{f,S}, [/mm] und die Belegung
[mm] x_1=0,\: x_2=1,\: x_4=1
[/mm]
erfuellt die Formel f.
Hoffentlich klaert das schon alles.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:35 Mi 01.03.2006 | | Autor: | Tyr7 |
Hallo,
jetzt ist alles klar. Der Fehler war, dass ich immer nur die gleichen Literale miteinander verbunden habe. Somit war der Graph ziemlich leer. Aber jetzt klappt es auch mit der Stabilen Menge :)
Nochmals danke und viele Grüße
Tyr
|
|
|
|
