Hamiltonian Path Finder

Pseudocode

No polynomial algorithm is known, so the honest formulation is backtracking with pruning. The pruning is what makes it usable at all.

HamiltonianPath(graph):
    for each start vertex s:
        if backtrack([s], {s}): return the path
    return none

backtrack(path, visited):
    if visited contains every vertex: return true

    u = path.last
    for each neighbor v of u not in visited:
        // Pruning that pays for itself:
        //  - any unvisited vertex now unreachable -> fail
        //  - two or more unvisited vertices of degree
        //    1 in the remaining graph -> fail
        visited.add(v)
        if backtrack(path + [v], visited): return true
        visited.remove(v)      // undo and try the next

    return false

The reachability prune is the one that matters most. After choosing a partial path, run a quick traversal over the unvisited vertices; if any is now cut off from the current endpoint, the branch is dead and can be abandoned immediately rather than after exploring a whole subtree. On sparse graphs this turns an intractable search into a fast one, even though the worst case remains exponential.

Worked example, step by step

Search for a Hamiltonian path from A on a five-vertex graph, and see why the same graph has no Hamiltonian cycle.

Example graph: Undirected edges A-B, B-C, C-D, D-E, plus the two chords A-C and B-D.

1. Degrees first. A has degree 2 (B and C), B has 3 (A, C, D), C has 3 (A, B, D), D has 3 (B, C, E), and E has degree 1, its only neighbour being D. A vertex of degree 1 must be an endpoint of any Hamiltonian path, which immediately tells us E is one end.
2. Try A to B first. From A take B, then from B take C, then from C the only unvisited neighbour is D, and from D the only unvisited one is E. That completes A-B-C-D-E covering all five vertices.
3. A second solution exists. Backtracking from A along the other branch gives A-C-B-D-E, also valid. Hamiltonian paths are frequently not unique, and an algorithm that returns the first one found is answering an existence question, not a counting one.
4. Now ask for a cycle. A Hamiltonian cycle would have to return from the final vertex to A. Both paths end at E, and E has degree 1 with its single edge going to D. There is no E-A edge, so no Hamiltonian cycle exists.

Two Hamiltonian paths exist, A-B-C-D-E and A-C-B-D-E, but no Hamiltonian cycle. The degree-1 vertex E settles both questions almost by itself: it forces itself to be a path endpoint, and it rules out any cycle, since a cycle requires every vertex to have degree at least 2. Checking degrees before searching is cheap and often decisive.

Complexity, and where it comes from

Time: O(V!) naive, O(V^2·2^V) with DP · Space: O(V·2^V) with DP

Naive backtracking explores permutations and is O(V!) in the worst case, which is hopeless beyond about 12 vertices. Held-Karp dynamic programming over subsets does much better: the state is a subset of visited vertices paired with the current endpoint, giving 2^V times V states, and each transition costs O(V), so the total is O(V squared times 2^V) time and O(V times 2^V) memory. That is practical to roughly 20 vertices, where 2^20 times 20 is about 20 million states. The problem is NP-complete, so no polynomial algorithm is expected to exist; pruned backtracking often finishes quickly on real sparse graphs despite the exponential worst case.

When to use Hamiltonian Path, and when not to

Confirm which problem you actually have before reaching for exponential machinery, because two of these are easy.

Common pitfalls

• Confusing it with the Eulerian problem. They sound similar and differ enormously. Eulerian covers edges and is linear; Hamiltonian covers vertices and is NP-complete. Solving the wrong one is the most expensive mistake available here.
• Searching without pruning. Pure backtracking with no reachability check explores vast dead subtrees. Testing that all unvisited vertices remain reachable from the current endpoint, and that at most two have degree 1 in the remaining graph, typically cuts the search by orders of magnitude.
• Assuming a path implies a cycle. A Hamiltonian path can exist while no Hamiltonian cycle does, exactly as in the example above. The cycle additionally requires an edge from the last vertex back to the first, and any vertex of degree 1 rules it out entirely.
• Trusting Dirac’s condition in reverse. Dirac says that if every vertex has degree at least V/2 then a Hamiltonian cycle exists. The converse is false: plenty of graphs with low degrees have Hamiltonian cycles, so failing the condition proves nothing.
• Expecting it to scale. Beyond roughly 20 to 25 vertices, an exact answer may simply be out of reach. If the real goal is a good route rather than a proof, model it as TSP and use heuristics.

Frequently asked questions

What is a Hamiltonian path?

A Hamiltonian path is a path that visits every vertex of a graph exactly once. If it also returns to its starting vertex it is a Hamiltonian cycle. Unlike an Eulerian path it does not need to use every edge, and it may not revisit any vertex.

Why is finding a Hamiltonian path hard?

Because the property cannot be checked locally. Eulerian paths are easy because a simple degree count at each vertex settles existence, but there is no comparable local test for visiting every vertex once. The problem is NP-complete, so no polynomial algorithm is known and finding one would resolve P versus NP.

What is the difference between Hamiltonian and Eulerian paths?

A Hamiltonian path visits every vertex exactly once and may ignore edges. An Eulerian path uses every edge exactly once and may revisit vertices. Eulerian existence is decidable in O(V + E) by counting odd-degree vertices; Hamiltonian existence is NP-complete.

How do you find a Hamiltonian path?

For small graphs, backtracking from each possible start with strong pruning: abandon a branch as soon as some unvisited vertex becomes unreachable, or once two or more unvisited vertices have degree 1 in the remaining graph. For up to about 20 vertices, Held-Karp dynamic programming over subsets gives a definitive answer in O(V squared times 2^V).

What is the relationship between Hamiltonian paths and TSP?

The travelling salesman problem is the weighted optimisation version: instead of asking whether a tour visiting every vertex exists, it asks for the cheapest one in a complete weighted graph. Deciding Hamiltonian cycle existence reduces to TSP, which is why TSP is also NP-hard.