28.18. Reduction of 3-SAT to Hamiltonian Cycle¶
28.18.1. 3-SAT to Hamiltonian Cycle¶
The following slideshow shows that an instance of the 3-CNF Satisfiability (3-SAT) problem can be reduced to an instance of Hamiltonian Cycle in polynomial time. A trivial change in the construction will allow reduction from 3-SAT to the Hamiltonian Path problem.
This reduction can help in providing an NP Completeness proof for the Hamiltonian Cycle problem.
