396. What is the Hamiltonian cycle problem, and how does it compare with finding an Eulerian circuit?
MediumComplexity classes
Technical
Show model answer
A Hamiltonian cycle visits every vertex exactly once and returns to the start. Deciding whether one exists is NP-complete: a proposed cycle is easy to verify, but no polynomial algorithm is known. Brute force tries up to (n − 1)!/2 orderings; the Held–Karp bitmask DP takes O(2ⁿ · n²) time and O(2ⁿ · n) space.
An Eulerian circuit uses every edge exactly once, and it is easy: a connected graph has one exactly when every vertex has even degree, and Hierholzer's algorithm finds it in O(V + E). The small change from 'every edge' to 'every vertex' moves the problem from linear time to NP-complete. Hamiltonian cycle also reduces to TSP: give edges weight 1 and non-edges weight 2, and ask for a tour of cost n.