CSCE 411 Lecture 33

Lecture Slides

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

Vertex Cover

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

Easy to find big vertex cover: let $V'$ 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'$, we can check in polynomial time if $|V'|\leq k$ and every edge has at least one endpoint in $V'$

Reduction to 3SAT

Let $C=c_{1}\wedge \dots \wedge c_{m}$ be any 3SAT input over the set of variables $U=\{u_{1},\ldots ,u_{n}\}$.

Construct $G$ like this:

• Two nodes for each variable: $u_{i}$ and $\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 \neg u_{3}\vee \neg u_{4})\wedge (\neg u_{1}\vee u_{2}\vee \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 {T} ,\mathbf {F} ,\mathbf {T} ,\mathbf {F} )$). 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