Course contentsShow
← Computer Science
Lesson 1935 of 2,87243. Complexity TheoryFree lesson

Vertex Cover and Clique Reductions

Explore reductions between Vertex Cover, Clique, and Independent Set showing their equivalence in complexity.

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.