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:
- Pick any already known NP-complete problem
- Reduce it to your new problem
- 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.