VL-15: NP-vollst¨andige Graphprobleme

Question 1

Wie funktioniert SAT ≤ CLIQUE?

Answer 1

• Für jedes Klausel c und jedes Literal l in dieser Klausel: Erzeuge einen Knoten
• Verbinde alle Knoten untereinander, die nicht aus der gleichen Klausel entstammen oder dessen Literale Negationen voneinander sind
• Setze k = Anzahl der Klauseln
• Wenn es eine Belegung für phi gibt, welche die k Klauseln erfüllt, dann gibt es auch eine k-Clique in G

Question 2

Wie funktioniert CLIQUE ≤ INDEP-SET

Answer 2

• Invertiere Kanten
• Wenn k-indipendent set, dann k-clique

Question 3

Wie funktioniert INDEP-SET ≤ VERTEX COVER?

Answer 3

• k = n-k, Vertex Cover set ist invers zu Independent Set

Question 4

Wie funktioniert SAT ≤ D-HAM-CYCLE?

Answer 4

• Für jede Variable x wird ein Diamantengadget erstellt
• Der Weg von RL wird als x = 1 interpretiert, LR mit x=0
• Für jede Klausel wird ein Knoten erstellt, welcher entweder RL verbunden wird, wenn x in c oder LR wenn ~x in c
• Wenn SAT erfüllbar ist, so gibt es einen D-HAM-CIRCLE. Jede Variable wird entweder LR oder RL durchlaufen und dabei werden alle Klauseln genau einmal besucht.