Hamiltonian Path

A Hamiltonian path visits every vertex of a graph exactly once; a Hamiltonian cycle additionally returns to the starting vertex. Deciding whether such a path exists is NP-complete, in sharp contrast to the Eulerian path, which is checkable in linear time.

How it works

Exact algorithms use backtracking: extend a partial path one vertex at a time, pruning when the current vertex has no unvisited neighbor. Dynamic programming over subsets (the same bitmask technique as Held-Karp) solves the problem in O(n squared times 2 to the n). Useful pruning rules include degree checks and connectivity tests of the remaining graph. For special graph classes, such as tournaments or graphs meeting Dirac or Ore degree conditions, existence is guaranteed and constructive algorithms exist.

Applications

Hamiltonian paths appear in genome assembly, circuit design and testing, puzzle games such as knight tours, and as the structural core of TSP. In interviews the bitmask dynamic programming solution is a standard hard question, and the contrast with the Eulerian path tests conceptual clarity.