Vertex Cover and Clique Reductions
You'll learn: How to prove Vertex Cover and Clique are NP-complete by reducing between them and Independent Set, revealing their deep structural equivalence.
The Core Insight
You've already seen that Vertex Cover, Clique, and Independent Set are all NP-complete problems. But they're not just independently hard—they're intimately connected through simple graph transformations. Understanding these reductions shows why these problems are really "the same problem in disguise."
Vertex Cover ↔ Independent Set
These two problems are complements on the same graph:
- A Vertex Cover of size k is a set of vertices touching every edge
- An Independent Set of size k is a set of vertices with no edges between them
The reduction: If S is a vertex cover of size k in graph G, then V - S (all vertices NOT in S) is an independent set of size n - k. Why? Because S touches every edge, so no edge can exist between vertices outside S.
Analogy: Think of a neighborhood watch. If k houses can see every street (vertex cover), then the remaining houses must all be invisible to each other (independent set).
Clique ↔ Independent Set
These problems are complements on opposite graphs:
- A Clique of size k in graph G is a set of vertices all connected to each other
- An Independent Set of size k in graph Ḡ (the complement graph—edges become non-edges and vice versa) is exactly the same set!
The reduction: Transform graph G to Ḡ by flipping edges. An independent set in G becomes a clique in Ḡ.
Why This Matters
These reductions prove that solving ANY one of these problems efficiently would solve ALL of them. They're all equally hard.
Key Takeaway: Vertex Cover, Clique, and Independent Set are polynomial-time equivalent—you can reduce any one to another in polynomial time, proving their shared NP-complete status and revealing their fundamental mathematical unity.