
We have seen the Vertex Cover problem (VC) and shown that it is in NP.
To show that VC is NPcomplete, it suffices to show that 3SAT ≤_{p} VC. We say that we show that VC is NPcomplete by reduction from 3SAT.
What we need is a polynomialtime computable function f that takes a formula φ with exactly 3 literals per clause and produces a pair (G, k) so that
φ is satisfiable  ⇔  G has a vertex cover of size ≤ k. 
Here is such a function f(φ).
Remember that f(φ) produces pair (G, k). First we show how to build graph G.
As a running example, consider formula φ = (x ∨ y ∨ ¬z) ∧ (¬y ∨ w ∨ z) ∧ (¬w ∨ ¬x ∨ y).
For each variable x in φ, create a pair of vertices called V_{x} and V_{x}.
Add an edge between V_{x} and V_{x}. These edges are called the variable edges.
For our example, we have this much of G:
w  —  w  x  —  x  y  —  y  z  —  z 
Suppose that the clauses in φ are c_{1}, …, c_{n}.
For each clause c_{i}, create three vertices C_{i,1}, C_{i,2} and C_{i,3}, and connect them together into a triangle.
The edges that make up the triangle are called the clause edges.
Suppose that clause c_{i} is (ℓ_{i, 1} ∨ ℓ_{i, 2} ∨ ℓ_{i, 3}). Write ℓ_{i,1} in vertex C_{i,1}, ℓ_{i,2} in vertex C_{i,3} ℓ_{i,3} in vertex C_{i,1}.
For our running example, we now have the following.
w  —  w  x  —  x  y  —  y  z  —  z  
x  y  w  
/  \  /  \  /  \  
y  —  z  w  —  z  x  —  y 
Now connect each variable node to every clause node that has the same literal written in it.
These edges are called the forcing edges.
That is all there is to graph G. But remember that f(φ) = (G, k).
If there are v variables and n clauses, choose k = 2n+v.
That fully describes the reduction function f(φ). But, in order to show that it works, we must show that
φ is satisfiable  ⇔  G has a vertex cover of size ≤ k. 
Suppose that φ is satisfiable. Choose an assignment A of values for the variables to make φ true.
For illustration, choose assignment A as follows for our running example.
w  =  false 
x  =  true 
y  =  false 
z  =  true 
We use assignment A to choose a vertex cover of size k = 2n+v of G.
For each pair of variable vertices V_{x} and V_{x},
add vertex V_{x} to the vertex cover if x is true in A, and
add V_{x} if x is false in A.
In the running example, vertices V_{w}, V_{x}, V_{y} and V_{z} are chosen.
That uses v vertices.
Notice that each variable vertex that is labeled by a true literal has been chosen.
Notice that all of the variable edges are covered.
Consider a clause c. At least one of the literals in clause c must be made true by assignment A.
Select one of the true literals and find the vertex for clause c that is labeled by that literal. Put the other two into the vertex cover.
That uses 2n vertices.
Since two vertices in each triangle have been chosen, all of the clause edges are covered.
In our running example, it suffices to choose clause vertices C_{1,y}, C_{1,z}, C_{2,w}, C_{2,z}, C_{3,x} and C_{3,y}.
That leaves clause vertices C_{1,x}, C_{2,y} and C_{3,w} unchosen.
We have put 2n + v vertices into the vertex cover, and that is all we get.
But we still need to cover the forcing edges.
The forcing edges that are incident on chosen clause vertices are obviously covered. But what about forcing edges that are incident on an unchosen clause vertex?
The unchosen clause vertex is labeled by a literal that is true under assignment A.
But the forcing edge goes to a variable vertex that is labeled by the same literal.
Since variable nodes labeled by true literals have been put into the vertex cover, those forcing edges are covered by a variable vertex.
In summary, we have used assignment A to find a vertex cover of G of size k. Obviously, then such a vertex cover exists.
Suppose that there exists a vertex cover of G that uses k = 2n+v vertices. Choose such a vertex cover S.
For our running example, suppose that S = {V_{x}, V_{y}, V_{z}, V_{w}, C_{1,x}, C_{1,z}, C_{2,vy}, C_{2,w}, C_{3,w}, C_{3,x}}.
We use S to find an assignment A of values to the variables that makes φ true.
Notice.
For each pair of variable vertices V_{x} and V_{x} in G, S must contain at least one of the vertices in that pair. Otherwise, the vertex edges are not covered.
S must also contain at least two vertices in each clause triangle. Otherwise, not all of the clause edges are covered.
But S only has 2n+v vertices, and that is just barely enough to cover all the vertex edges and all of the clause edges.
So for each pair of vertex nodes V_{x} and V_{x}, exactly one must be in S.
Similarly, for each clause triangle, exactly two of its vertices must be in S.
Choose assignment A as follows.
Make x true if vertex V_{x} is in S.
Make x false if V_{x} is not in S.
Since S is a vertex cover of G, it must cover all of the forcing edges.
For each clause c, there is one vertex u in that clause's triangle that is not in S. So the other end of the forcing edge that hits u must be in S.
But the other end is a variable vertex, and it is labeled by the same literal ℓ as clause vertex u. Since value assignment A makes ℓ true, clause c has a true literal, namely ℓ.
