CSCE 411 Lecture 33

Lecture Slides

« previous | Wednesday, November 14, 2012 | next »

Vertex Cover

given undirected graph $G=(V,E)$, $V^{\prime }\subseteq V$ is a vertex cover iff every edge in $E$ has at least one endpoint in $V^{\prime }$

Easy to find big vertex cover: let $V^{\prime }$ be all nodes. What about smaller vertex cover?

Decision Problem: Given a graph G and an integer $k$, does $G$ have a vertex cover of size at most $k$?

VC ∈ NPC

VC ∈ NP: given a candidate solution $V^{\prime }$, we can check in polynomial time if $|V^{\prime }|\le k$ and every edge has at least one endpoint in $V^{\prime }$

Reduction to 3SAT

Let $C=c_1\wedge \dots \wedge c_m$ be any 3SAT input over the set of variables $U=\{u_1,\dots ,u_n\}$.

Construct $G$ like this:

• Two nodes for each variable: $u_i$ and $\mathrm{\neg }{u}_i$ with an edge between them ("literal" nodes)
• Three nodes fro each clause $c_j$, "placeholders for the three literals in the clause: $a_j^1$ $a_j^2$, $a_j^3$ with edges making a triangle
• edges connecting each placeholder node in a triangle to the corresponding literal node
• Set $k=n+2m$

Example

3SAT vars $u_1$, ..., $u_4$ and clauses $(u_1\vee \mathrm{\neg }{u}_3\vee \mathrm{\neg }{u}_4)\wedge (\mathrm{\neg }{u}_1\vee u_2\vee \mathrm{\neg }{u}_4)$

$k=4+2\cdot 2=8$

Suppose the 3SAT input (with $m$ clauses over $n$ vars) has a satisfying truth assignment (e.g. $(u_1,u_2,u_3,u_4)=(\mathbf{𝐓},\mathbf{𝐅},\mathbf{𝐓},\mathbf{𝐅})$). Show that there is a VC of $G$ of size $n+2m$:

• pick node in each pair corresponding to the true literal w.r.t. the satisfying truth assignment
• pick 2 nodes in each triangle such that the excluded node is connected to a true literal