11.18. Reduction of 3-SAT to Hamiltonian Cycle (optional) (WORK IN PROGRESS)¶
11.18.1. 3-SAT to Hamiltonian Cycle¶
The following slideshow shows that an instance of 3-CNF Satisfiability problem can be reduced to an instance of Hamiltonian Cycle problem in polynomial time.
This reduction can help in providing an NP Completeness proof for the Hamiltonian Cycle problem.
