Vertex Cover

Algorithmic graph theory proves to be a fertile ground for hard problems. The prototypical NP-complete graph problem is vertex cover, previously defined in Section as follows:  

Input: A graph G=(V, E) and integer .

Output: Is there a subset S of at most k vertices such that every has at least one vertex in S? Demonstrating the hardness of vertex cover proves more difficult than the previous reductions we have seen, because the structure of the two relevant problems is very different. A reduction from 3-satisfiability to vertex cover has to construct a graph G and bound k from the variables and clauses of the satisfiability instance.

First, we translate the variables of the 3-SAT problem. For each Boolean variable , we create two vertices and connected by an edge. To cover these edges, at least n vertices will be needed, since no two of the edges will share a vertex.

 
Figure: Reducing satisfiability instance to vertex cover  

Second, we translate the clauses of the 3-SAT problem. For each of the c clauses, we create three new vertices, one for each literal in each clause. The three vertices of each clause will be connected so as to form c triangles. At least two vertices per triangle must be included in any vertex cover of these triangles.

Finally, we will connect these two sets of components together. Each literal in the vertex ``gadgets'' is connected to corresponding vertices in the clause gadgets (triangles) that share the same literal. From a 3-SAT instance with n variables and c clauses, this constructs a graph with 2n+3c vertices. The complete reduction for the 3-SAT problem is shown in Figure .

This graph has been designed to have a vertex cover of size n+2c if and only if the original expression is satisfiable. By the earlier analysis, any vertex cover must have at least n+2c vertices, since adding extra edges to the graph can only increase the size of the vertex cover. To show that our reduction is correct, we must demonstrate that:

• Every satisfying truth assignment gives a vertex cover - Given a satisfying truth assignment for the clauses, select the n vertices from the vertex gadgets that correspond to literals to be members of the vertex cover. Since this is a satisfying truth assignment, a true literal from each clause will have covered one of the three cross edges connecting each clause triangle to a vertex gadget. Therefore, by selecting the other two vertices of each clause triangle, we can also pick up the remaining cross edges and complete the cover.
• Every vertex cover gives a satisfying truth assignment - Given any vertex cover C of size n+2c, exactly n of the vertices must belong to the vertex gadgets. Let these first stage vertices define the truth assignment, while the 2c remaining cover vertices must be distributed at two per clause gadget; otherwise a clause gadget edge must go uncovered. These clause gadget vertices can cover only two of the three connecting cross edges per clause. Therefore, if C gives a vertex cover, at least one cross edge per clause must be covered, meaning that the corresponding truth assignment satisfies.

This proof of the hardness of vertex cover, chained with the clique and independent set arguments of Section , gives us a library of hard graph problems that we can use to make future hardness proofs easier.