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)

▶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.

[EasyTheory]

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su

[MatthiasGN]

This guy brings the best energy. Hardest NP-complete reduction on the planet? Well, it's actually Very Easy. 😂

[arielhy]

Dude! English is not even my first language and still ONLY YOU made sense of what is happening here to me. Thank you so much!
I think you should consider adding "reduction from SAT" to the title since that is mainly what you explain here, so brightly. Bless you

[brendawilliams]

Thankyou it hadn’t occurred to me to me. Great explanation

[isithasubasinghe]

Thanks for taking the time to make these videos :)

Any chance you could cover TSP approximation algorithms? k-opt in particular would be interesting

Thanks

[luisalazago]

Good video bro, thanks for explaining the proof.

But you should prove the Hamiltonian path is NP-Complete transforming from the VERTEX-COVER to Hamiltonian path. It's an interesting way to prove the same that you did.

[SomduttaSomSinha]

Isn't a clause node visited multiple times by each variable gadget in that clause? Doesn't that mean that it is an invalid Hamilton path as a node is visited more than once? For example, if we had c_1 = ((X1) OR (NOT X2) OR (X3)), the variable gadgets corresponding to X1, X2 and X3 will all visit the node corresponding to c_1

[LENOKOK]

thank you so much for your work!! I spend hours watching your videos when working on my homework :)

[suindude]

The edging of Hamiltonian path which has extreme resemblance with the ckt, we may observe in the case of Logistics management an algorithm goes to a differentiated phenomena to the reduction for a given set of time and the drilled down variability waxing waning with time complexity shows a NP completeness at high.

[ytpah]

If each clause is represented by a single node wouldn't that clause node be visited more than once if two or more of the elements in a clause are satisfied? I think you need a clause gadget.

[brendawilliams]

I hope for more videos it is interesting

[kennyanthony]

My goodness is this channel wonderful!

[jiaweiliu]

Thank you!! This explanation is so clear.

[brendawilliams]

I was wondering why you would want such a thing too.

[-Molo-]

I didn't know charlie puth taught comp sci