Hamiltonian Path is NP-Complete (Directed, Reduction from 3SAT)

Here we show that the directed hamiltonian path problem is NP-complete by showing it is in NP and is NP-hard via a polynomial-time reduction from the 3SAT problem. The key in the reduction is to embed the variables and clauses of the formula as "gadgets" and connect them up in a useful way. Each of the possible "paths" through the variable gadgets corresponds to a variable assignment.

(The thumbnail background comes courtesy of the Sipser textbook)

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.