5.2Reductions and classic NP-complete problems
The idea
A polynomial reduction turns instances of one problem into instances of another. To show a problem is hard, reduce a known hard problem to it.
Think of it like this: Translating a puzzle into another puzzle: if you could solve the second one quickly, you could solve the first.
Why it exists
The direction of reductions is the favourite trap.
How it works
- A ≤ₚ B: an algorithm for B gives one for A.
- To prove B NP-hard: pick a known NP-hard A and show A ≤ₚ B.
- If B ∈ P and A ≤ₚ B, then A ∈ P.
- Chain: SAT → 3-SAT → Clique → Independent set → Vertex cover.
Worked example: Clique ≤ₚ Independent set
Complement the graph: a clique in G is an independent set in the complement, so an independent-set solver solves clique.
Now play with it
- →Read the reduction table row by row.
- →Say each rule aloud with A and B swapped to see how it would become false.
| Reduction | Direction to remember |
|---|---|
| SAT ≤ₚ 3-SAT | convert long clauses with extra variables |
| 3-SAT ≤ₚ Clique | one vertex per literal, join compatible literals from different clauses |
| Clique ≤ₚ Independent set | complement the graph |
| Independent set ↔ Vertex cover | complement sets: S independent ⇔ V − S is a cover |
| Hamiltonian cycle ≤ₚ TSP | weight 1 for edges, 2 for non-edges |
| To prove B is NP-hard | reduce a known NP-hard problem A to B (A ≤ₚ B) |
| If A ≤ₚ B and B ∈ P | then A ∈ P |
| If A ≤ₚ B and A is NP-hard | then B is NP-hard |
Cook-Levin theorem: SAT is NP-complete, the first problem proved so. All others follow by reductions.
Check yourself
To prove problem X is NP-hard, you should reduce
Exam notes (the dense version)
A polynomial-time reduction A ≤ₚ B converts instances of A into instances of B. To prove B is NP-hard, reduce a known NP-hard problem to B (the direction matters). The first NP-complete problem is SAT (Cook-Levin). Chain: SAT → 3-SAT → Clique / Independent Set / Vertex Cover → Hamiltonian Cycle → TSP (decision), Subset Sum, 3-Colouring.