Algorithms for NP-Hard Problems (Section 22.5: Directed Hamiltonian Path Is NP-Hard)

Reduction from the 3-SAT problem to the Directed Hamiltonian Path problem.

[Dontonethefirst]

Thanks for posting these videos it really helps in thinking about these things.

[deopen]

I think there should be 3m+1 internal vertices acording to the sipser (Chapter 7), because for each pair we need a seperator vertex. If we didnt, we probably can visit a clause gadget which we should not able to visit. Imagine we visit the clause vertex with a second edge and come back to the next vertex of internal chain with another second edge. By second edge i mean the edge that we encounter as a second edge of clause vertex when we are traversing the internal chain of diamond.

[gregorymorse]

It's disappointing to see the wrong solution presented so much everywhere. It feels like someone respected made a mistake and everyone copied it. I won't be kind as this mistake annoys me profusely and I want to see it eliminated. 3k+3 not 2k per vertex. Period. Unless you want to prove the clause gadgets enforce edge order, which you wont