Algorithms for NP-Hard Problems (Section 22.5: Directed Hamiltonian Path Is NP-Hard)
Tim Roughgarden Lectures · 26:24
This lecture (Algorithms Illuminated Part 4, §22.5) proves directed Hamiltonian path is NP-hard by reducing 3SAT to it: a necklace of “diamond” gadgets encodes variable assignments as up/down traversals, and clause ve...