Vertex Cover etc.

Def: M $\subseteq$ V ist Knotenüberdeckung für G = (V, E), wenn $\forall$xy $\in$ E : x $\in$ M $\vee$ y $\in$ M.

Def: VC = {(G, k) | $G$ besitzt Knotenüberdeckung der Größe $k$}

Satz: VC $\in$ NPC.

Beweis: 1. VC $\in$ NP (M raten und verifizieren) 2. 3SAT$\le_{P}^{}$VC durch folgende Übersetzungsfunktion

f : 3-KNF-Formel $\to$ Graph × Zahl

• für jede Variable v zwei Knoten v, v', durch Kante verbunden
• für jede Klausel k drei Knoten k₁, k₂, k₃, auf einem C₃,
• für jedes positive Vorkommen einer Variablen v in einer Klausul-Position k_i eine Kante vk_i, für jedes negative Vorkommen eine Kante v'k_i.
• die Zahl k = Anzahl der Variablen von F +2 Anzahl der Klauseln von F.

Behauptung: f ist in P-Zeit berechenbar und für jede Formel F: F $\in$ 3SAT$\iff$f (F) $\in$ VC

Zu zeigen sind beide Richtungen:

• aus erfüllender Belegung F konstruiere Knotenüberdeckung für f (F)
• aus Knotenüberdeckung für f (F) konstruiere erfüllende Belegung für F.

VC für Graphen von Maixmalgrad 3 auch noch NP-vollständig.

IS = {(G, k) | $G$ besitzt unabh. Menge der Größe $k$}

CLIQUE = {(G, k) | $G$ besitzt Clique der Größe $k$}

Aufgaben:

• VC$\le_{P}^{}$IS, VC$\le_{P}^{}$CLIQUE
• Komplexität dieser Probleme für a) planare Graphen, b) bipartite Graphen, c) Bäume