INDEPENDENT-SET ≤p CLIQUE

A textbook polynomial-time reduction via graph complementation. The same vertex set is an independent set in G iff it is a clique in the complement G̅.

The two problems

INDEPENDENT-SET

Instance: An undirected graph G and a positive integer k.

Question: Does G contain a set of k vertices with no edge between any two of them?

CLIQUE

Instance: An undirected graph G′ and a positive integer k.

Question: Does G′ contain a set of k vertices with every pair connected by an edge?

The construction

Given an INDEPENDENT-SET instance ⟨G, k⟩, build a CLIQUE instance ⟨G′, k⟩ where G′ is the complement of G:

G′ has the same vertex set as G.
For every pair u ≠ v of vertices: u–v is an edge of G′ iff u–v is not an edge of G.
Use the same threshold k.

Building the complement examines each of the n(n−1)/2 pairs once, so the reduction runs in O(n²) time.

Visualization

Step 1 / 4INDEPENDENT-SET instance

Input ⟨G, k⟩ with k = 3. The highlighted vertices S = {1, 3, 5} form an independent set in G — no edge of G has both endpoints in S.

Correctness

(⇒) If S ⊆ V(G) is an independent set of size k in G, then no edge of G has both endpoints in S. By the definition of the complement, every pair in S has an edge in G′. So S is a clique of size k in G′.

(⇐) If S ⊆ V(G′) is a clique of size k in G′, then every pair in S has an edge in G′, i.e., no pair in S has an edge in G. So S is an independent set of size k in G.

Hence ⟨G, k⟩ ∈ INDEPENDENT-SET iff ⟨G′, k⟩ ∈ CLIQUE, and the map G ↦ G′ is computable in polynomial time. ∎