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

Reduction Chains

Understand how multiple reductions can be chained together and how transitivity preserves NP-completeness.

Reduction Chains

You'll learn how to chain multiple reductions together to prove NP-completeness efficiently.

The Core Idea

You've seen individual reductions proving problems are NP-complete (like SAT → 3-SAT, then 3-SAT → Independent Set). A reduction chain is when you string these together: if problem A reduces to B, and B reduces to C, then A automatically reduces to C. This is called transitivity of reductions.

Think of it like a chain of translators: if you can translate English to French, and French to Spanish, then you can translate English to Spanish by going through French as an intermediate step.

Why Chains Matter

Once you've proven one problem is NP-complete (historically, SAT via the Cook-Levin theorem), you don't need to reduce directly from SAT every time. Instead, you can:

  1. Pick any already known NP-complete problem
  2. Reduce it to your new problem
  3. Your new problem is now NP-complete too!

For example:

  • SAT → 3-SAT → Independent Set → Vertex Cover → Clique

Each arrow is a polynomial-time reduction. Because polynomial times compose (multiply together and stay polynomial), the entire chain preserves NP-completeness.

Transitivity Preservation

If A ≤ₚ B and B ≤ₚ C (where ≤ₚ means "polynomial-time reduces to"), then A ≤ₚ C. The running time is the product of the individual reduction times, which remains polynomial. This means NP-completeness "flows through" the chain—if the starting problem is NP-complete and your problem is at the end, it's NP-complete too.

Key Takeaway: Reduction chains let you prove NP-completeness by reducing from any known NP-complete problem, not just SAT, because transitivity preserves the hardness property through polynomial-time transformations.