12.4. The Vertex Cover Problem is NP-complete

The Vertex Cover problem (VC)

---

We have seen the Vertex Cover problem (VC) and shown that it is in NP.

To show that VC is NP-complete, it suffices to show that 3-SAT ≤_p VC. We say that we show that VC is NP-complete by reduction from 3-SAT.

3-SAT ≤_p VC

---

What we need is a polynomial-time computable function f that takes a formula φ with exactly 3 literals per clause and produces a pair (G, k) so that

A reduction

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).

1. 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

    

2. Suppose that the clauses in φ are c₁, …, 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

    

3. 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.

Why the reduction works

---

That fully describes the reduction function f(φ). But, in order to show that it works, we must show that

(⇒)

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.

We use assignment A to choose a vertex cover of size k = 2n+v of G.

1. For each pair of variable vertices V_x and V_x,

   1. add vertex V_x to the vertex cover if x is true in A, and

   2. 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.

2. 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.

3. 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.

1. Make x true if vertex V_x is in S.

2. 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 ℓ.