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