Lecture 16 - Classic NP-Complete Reductions
(Skeleton for Fall 2026.)
The Reduction Toolkit
TODO: gadget thinking; what a reduction must and must not do; the write-up template required on problem sets (map, forward direction, backward direction, polynomial time).
The Classic Chain
TODO: SAT to 3SAT to CLIQUE to VERTEX-COVER; 3SAT to HAMPATH; SUBSET-SUM. Pick 3-4 to do fully in lecture, leave the rest as problem set material.
Coping with NP-Completeness
TODO: brief honest survey: exact exponential algorithms, approximation, heuristics, parameterized tractability; one slide each, pointers only.