        Next: Clique and Independent Set Up: Simple Reductions Previous: Hamiltonian Cycles

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