P28 · CLIQUE → VC

1 · The complement-graph duality

VERTEX-COVER = {⟨G, k⟩ : G has a vertex cover of size ≤ k}, where a vertex cover is a set S of vertices that touches every edge — for each edge (u, v), at least one of u, v is in S.

The duality lemma · Sipser Theorem 7.44

Let G be a graph on n vertices, and let G̅ be its complement (same vertices, edges flipped: uv is an edge of G̅ iff uv is not an edge of G). Then S is a clique of size k in G if and only if V \ S is a vertex cover of size n − k in G̅.

The reduction: f(⟨G, k⟩) = ⟨G̅, n − k⟩. Computing G̅ takes O(n²) time. Polynomial, so this is a many-one reduction. Since CLIQUE is NP-complete and CLIQUE ≤_p VERTEX-COVER, VERTEX-COVER inherits NP-hardness. VERTEX-COVER ∈ NP (the cover is a polynomial-size witness), so it is NP-complete.

Why the duality works

A clique S in G means every pair in S is connected in G — equivalently, no pair in S is connected in G̅. So no edge of G̅ has both endpoints in S, which means every edge of G̅ has at least one endpoint outside S, which means V \ S is a vertex cover of G̅. The argument is symmetric in both directions.

🔊 Listen

2 · Animated demo · auto-plays · loops

4 · Pitfalls

The complement is the edge complement, not the vertex complement. G̅ has the same vertex set as G; only edges flip. Easy to confuse with "remove vertices from G."
The size flips: k becomes n − k. Pay attention. A clique of size 3 in a 7-vertex graph becomes a vertex cover of size 4. Off-by-one with n vs n−1 is a common bug.
This is a many-one reduction in both directions. CLIQUE ≡_p VERTEX-COVER. The two problems are essentially the same up to complement. So they share NP-completeness or P-membership together.
Vertex cover ≠ vertex set covering edges in some other sense. Specifically: every edge needs at least one endpoint in the cover. Not "every vertex is covered" or "the cover covers something else."

5 · Q&A defence notes

Q1. Why does the complement work?
Edges of G connect clique-members (every pair in S has an edge). Edges of G̅ are exactly the non-edges of G — so they have no both-endpoints-in-S edges, which means every edge of G̅ has at least one endpoint outside S. That outside set V\S is a vertex cover of G̅.
Q2. How long does the reduction take?
Computing G̅ by iterating all pairs takes O(n²) time. Computing n − k is O(1). Total O(n²) — polynomial.
Q3. Is this also a reduction from VERTEX-COVER to CLIQUE?
Yes, by symmetry of the lemma. f(⟨G, m⟩) = ⟨G̅, n − m⟩ reduces VERTEX-COVER to CLIQUE. The two problems are polynomial-time equivalent.
Q4. What's the chain so far?
3SAT ≤_p CLIQUE (P27) ≤_p VERTEX-COVER (this problem). All three NP-complete. The chain continues: VERTEX-COVER ≤_p HAMPATH ≤_p SUBSET-SUM ≤_p ...

6 · Where to read more

Sipser: Theorem 7.44 (CLIQUE ≤_p VERTEX-COVER). Lecture notes: Module 5 slide 5. Companion problems: P27 (3SAT → CLIQUE), P31 (3-COLOR — another graph-theoretic NP-complete).