Skip to interview prep
Apexed

237. Why is finding a Hamiltonian cycle considered hard, and what can you do in practice?

HardGraph algorithms

Technical
Show model answer

Deciding whether a graph has a cycle visiting every vertex exactly once is NP-complete (it is one of the classic problems reduced from 3-SAT or vertex cover). A certificate (the cycle) is easy to verify, but no polynomial algorithm is known, and one would imply P = NP.

Exact approaches: backtracking with pruning, O(n!) worst case, or the Held-Karp bitmask DP over (visited set, last vertex) in O(n²·2ⁿ) time and O(n·2ⁿ) space, practical up to about 20-25 vertices. Sufficient conditions such as Dirac's theorem (every degree ≥ n/2 for n ≥ 3) guarantee a Hamiltonian cycle.

Why is finding a Hamiltonian cycle considered hard, and what can you do in practice — Data structures & algorithms interview question — Apexed