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: [ Ссылка ]
▶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.
