Independent Set and Vertex Cover

 

The vertex cover problem, discussed more thoroughly in Section , asks for a small set of vertices that contacts each edge in a graph. More formally:  

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?

 
Figure: Circled vertices form a vertex cover, the dark vertices an independent set  

It is trivial to find a vertex cover of a graph, for the cover can consist of all of the vertices. More tricky is to cover the edges using as small a set of vertices as possible. For the graph of Figure , four of the eight vertices are sufficient to cover.

A set of vertices S of graph G is independent if there are no edges (x,y) where and , meaning there are no edges between any two vertices in the independent set. As discussed in Section , the independent set problem arises in facility location problems. The maximum independent set decision problem is formally defined:  

Input: A graph G and integer .

Output: Does there exist an independent set of k vertices in G? Both vertex cover and independent set are problems that revolve around finding special subsets of vertices, the first with representatives of every edge, the second with no edges. If S is the vertex cover of G, the remaining vertices S-V must form an independent set, for if there were an edge with both vertices in S-V, then S could not have been a vertex cover. This gives us a reduction between the two problems:

VertexCover(G,k)

		 G' = G

		 k' = |V| - k

		 Return the answer to IndependentSet(G',k')

Again, a simple reduction shows that the problems are identical. Notice how this translation occurs without any knowledge of the answer. We transform the input, not the solution. This reduction shows that the hardness of vertex cover imples that independent set must also be hard. It is easy to reverse the roles of the two problems in this reduction, thus proving that both of these problems are equally hard.