CLIQUE ≤p INDEPENDENT-SET
The reverse direction, also via graph complementation. Together with INDEPENDENT-SET ≤p CLIQUE, this shows the two problems are polynomial-time equivalent.
The two problems
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?
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?
The construction
Given a CLIQUE instance ⟨G, k⟩, build an INDEPENDENT-SET 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 / 4CLIQUE instance
Input ⟨G, k⟩ with k = 3. The highlighted vertices S = {1, 3, 5} form a clique in G — every pair is connected by an edge.
Correctness
(⇒) If S ⊆ V(G) is a clique of size k in G, then every pair in S has an edge in G. By the definition of the complement, no pair in S has an edge in G′. So S is an independent set of size k in G′.
(⇐) If S ⊆ V(G′) is an independent set of size k in G′, then no pair in S has an edge in G′, i.e., every pair in S has an edge in G. So S is a clique of size k in G.
Hence ⟨G, k⟩ ∈ CLIQUE iff ⟨G′, k⟩ ∈ INDEPENDENT-SET, and the map G ↦ G′ is computable in polynomial time. ∎