Independent Set to Vertex Cover (Karp Reduction)

Definition

Independent Set to Vertex Cover

There is a polynomial-time many-one reduction from the Independent Set problem to the Vertex Cover problem:

Construction

Given an independent set instance with and , output the vertex cover instance

The graph remains unchanged. Only the threshold changes because a set and its complement satisfy

The orange independent set on the left becomes the unselected vertices on the right. Its complement is orange on the right and touches every edge.

Correctness

The graph has an independent set of size at least if and only if it has a vertex cover of size at most .

Correctness

Forward

Suppose that has an independent set with . Let . Since no edge has both endpoints in , every edge has at least one endpoint in . Thus, is a vertex cover, and

Hence, is a yes-instance of Vertex Cover.

Backward

Suppose that has a vertex cover with . Let . If two vertices in were adjacent, their edge would have no endpoint in , contradicting that is a vertex cover. Hence, is independent, and

Therefore, is a yes-instance of Independent Set.

Running time

The reduction counts the vertices, computes , and copies the graph without changing its edges. It therefore runs in time, which is polynomial in the input size.

NP-completeness

Independent Set is NP-hard, so this reduction proves that Vertex Cover is NP-hard. Together with membership in NP, this proves that Vertex Cover is NP-complete.