25.17. Reduction of 3-SAT to Hamiltonian Cycle¶
25.17.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.
