## 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

 φ is satisfiable ⇔ G has a vertex cover of size ≤ k.

### 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 φ = (xy ∨ ¬z) ∧ (¬ywz) ∧ (¬w ∨ ¬xy).

1. For each variable x in φ, create a pair of vertices called Vx and Vx.

Add an edge between Vx and Vx. 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 c1, …, cn.

For each clause ci, create three vertices Ci,1, Ci,2 and Ci,3, and connect them together into a triangle.

The edges that make up the triangle are called the clause edges.

Suppose that clause ci is (ℓi, 1 ∨ ℓi, 2 ∨ ℓi, 3). Write ℓi,1 in vertex Ci,1, ℓi,2 in vertex Ci,3i,3 in vertex Ci,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

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

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

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

2. add Vx if x is false in A.

In the running example, vertices Vw, Vx, Vy and Vz 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 C1,y, C1,z, C2,w, C2,z, C3,x and C3,y.

That leaves clause vertices C1,x, C2,y and C3,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 = {Vx, Vy, Vz, Vw, C1,x, C1,z, C2,vy, C2,w, C3,w, C3,x}.

We use S to find an assignment A of values to the variables that makes φ true.

Notice.

• For each pair of variable vertices Vx and Vx 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 Vx and Vx, 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 Vx is in S.

2. Make x false if Vx 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 ℓ.