Hamiltonian Path, in depth

The problem, precisely

Fix the variants first, because mixing them up is the most common bug.

• Path versus cycle. A Hamiltonian cycle also returns to its start. Every cycle yields a path, not the reverse: a simple line graph has a path and no cycle.
• Undirected versus directed. Directed steps follow edge direction; the algorithms work for both, with small pruning changes.
• Free or fixed endpoints. The path may have to start at s, or run from s to t.

Directed Hamiltonian cycle was one of Karp's original 21 NP-complete problems in 1972, and the path and undirected versions are NP-complete as well, via small reductions. One worth knowing: a graph G has a Hamiltonian path if and only if G plus one new vertex joined to every original vertex has a Hamiltonian cycle. In practice NP-completeness means three things: expect exponential worst cases, exploit structure in your actual inputs, and know the size at which each exact method stops being feasible.

The weighted optimisation version is the travelling salesman problem (see TSP with dynamic programming); here we only ask whether a path exists.

Backtracking from first principles

The search grows a path one vertex at a time. The state is the current path and the set of used vertices. From the last vertex, try each unused neighbour; if the path reaches all n vertices, stop. If no neighbour works, undo the last step and try the next option. This is the choose, explore, unchoose template from backtracking in general, applied to a graph.

def ham_path_plain(adj, n):
    # adj: list of sets of neighbours. Returns a path (list of vertices) or None.
    path, used = [], [False] * n

    def extend(u):
        if len(path) == n:
            return True
        for v in adj[u]:
            if not used[v]:
                used[v] = True; path.append(v)        # choose
                if extend(v):                         # explore
                    return True
                path.pop(); used[v] = False           # unchoose
        return False

    for s in range(n):                                # free endpoints: try every start
        used[s] = True; path.append(s)
        if extend(s):
            return path
        path.pop(); used[s] = False
    return None

The worst case visits every simple path, on the order of n factorial in a dense graph. A path that has already split the unvisited vertices into two disconnected groups is dead, yet plain backtracking explores all of its continuations before finding out.

Pruning that changes the picture

Four rules do almost all of the useful pruning for undirected graphs. Each one is cheap compared with the subtree it removes.

1. Reachability. Every unvisited vertex must be reachable from the current end through unvisited vertices. One BFS or DFS per search node, costing O(V + E), detects a path that has split the remaining graph. The traversal itself is covered in BFS and DFS.
2. Dead ends. Count, for each unvisited vertex, its neighbours that are unvisited or equal to the current end. A count of 0 means it can never be reached. A count of 1 means it must be the final vertex of the path, and only one vertex can be final. So two or more such vertices kill the branch. Applied before the search starts, the same rule says that a graph with three or more degree-1 vertices has no Hamiltonian path.
3. Start at a forced endpoint. A degree-1 vertex must be an endpoint, so try starting from vertices in ascending order of degree. If one exists, the search finds a path starting there or proves that none exists.
4. Warnsdorff ordering. Try next the neighbour with the fewest unvisited neighbours of its own. Vertices with few options are the ones most likely to be stranded, so visit them while they can still be reached. This is a heuristic for ordering only; it never removes a branch.

def ham_path(adj, n):
    path, used = [], [False] * n

    def feasible(last):
        seen, stack = {last}, [last]                  # rule 1: reachability
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not used[v] and v not in seen:
                    seen.add(v); stack.append(v)
        if len(seen) - 1 != n - len(path):
            return False
        ends = 0                                      # rule 2: dead ends
        for v in range(n):
            if not used[v]:
                d = sum(1 for w in adj[v] if not used[w] or w == last)
                if d == 0:
                    return False
                if d == 1:
                    ends += 1
                    if ends > 1:
                        return False
        return True

    def extend(u):
        if len(path) == n:
            return True
        if not feasible(u):
            return False
        nxt = [v for v in adj[u] if not used[v]]
        nxt.sort(key=lambda v: sum(1 for w in adj[v] if not used[w]))   # rule 4
        for v in nxt:
            used[v] = True; path.append(v)
            if extend(v):
                return True
            path.pop(); used[v] = False
        return False

    for s in sorted(range(n), key=lambda v: len(adj[v])):               # rule 3
        used[s] = True; path.append(s)
        if extend(s):
            return path
        path.pop(); used[s] = False
    return None

For directed graphs, follow edge directions in rule 1, and in rule 2 reject vertices that cannot be entered and allow at most one with no way out.

Worked example with measured node counts

Take the eight-vertex graph in the figure, with edges A-B, A-C, B-C, B-D, C-E, D-E, D-F, E-F, F-G and A-H.

G and H have degree 1, so any Hamiltonian path must run between them. The pruned solver starts at G (lowest degree first) and walks G, F, D, E, C, B, A, H, making 8 recursive calls: one per vertex, with no backtracking at all. The plain solver starts at A, the first vertex in index order, and every path starting at A is doomed, because A is not an endpoint. It makes 232 calls in total.

Now add a vertex I attached only to D. There are three degree-1 vertices, and only two can be endpoints, so no Hamiltonian path exists. The pruned solver rejects each of the nine starting vertices in its first feasibility check, for 9 calls in total. The plain solver has to exhaust the search space and makes 357 calls to reach the same answer.

Small graphs flatter any method, so we also generated 40 random 14-vertex graphs with edge probability 0.22 and kept the 30 with no Hamiltonian path, the expensive case. Across them the plain solver made 152,568 calls and the pruned solver 579. That is a measurement on random inputs, not a guarantee; adversarial families defeat these rules and the worst case stays exponential.

Exact dynamic programming over subsets

When n is small enough for 2ⁿ states to fit in memory, an exact dynamic program over subsets removes the dependence on luck. Let reach[mask] be the set of vertices v where some path visits exactly mask and ends at v. Start with every single-vertex mask. A path covering mask and ending at u extends to any neighbour v of u outside mask. A Hamiltonian path exists if and only if reach[full] is not empty. Storing each reach entry as a bitset (an integer) keeps the table small.

def ham_path_dp(adj, n):
    nbr = [sum(1 << v for v in adj[u]) for u in range(n)]   # neighbour bitsets
    full = (1 << n) - 1
    reach = [0] * (1 << n)
    for v in range(n):
        reach[1 << v] = 1 << v
    for mask in range(1, full + 1):            # increasing order: subsets come first
        ends = reach[mask]
        u = 0
        while ends:
            if ends & 1:
                out = nbr[u] & ~mask
                while out:
                    b = out & -out             # lowest set bit = one new vertex
                    reach[mask | b] |= b
                    out ^= b
            ends >>= 1; u += 1
    if not reach[full]:
        return None
    mask = full                                # walk backwards to recover a path
    v = (reach[full] & -reach[full]).bit_length() - 1
    path = [v]
    while mask != 1 << v:
        mask ^= 1 << v
        cand = reach[mask] & nbr[v]            # some end of the smaller path touches v
        v = (cand & -cand).bit_length() - 1
        path.append(v)
    return path[::-1]

This is the same subset technique as Held-Karp for TSP, minus the weights. It takes O(2ⁿ n²) time in the form above, and O(2ⁿ n) if the transition is written with word-level bit operations. It uses O(2ⁿ) words of memory. At n = 25 that is about 33.5 million entries, around 134 MB at four bytes each in a compiled language. Beyond the mid-twenties the memory and time grow out of reach. Its running time does not depend on the answer.

We cross-checked all three solvers on 300 random graphs with 2 to 11 vertices: every existence answer agreed and every returned path verified edge by edge.

When the problem is easy

Several graph classes have guaranteed or fast answers, so check whether your input belongs to one before reaching for exponential search.

• Directed acyclic graphs. A DAG has a Hamiltonian path if and only if its topological order is unique, which you can test by checking that each consecutive pair in one topological order is joined by an edge. That is O(V + E).
• Tournaments. A directed graph with exactly one edge between every pair always has a Hamiltonian path (Rédei's theorem), built by inserting vertices one at a time.
• Dense graphs. Dirac's theorem: if n ≥ 3 and every vertex has degree at least n/2, the graph has a Hamiltonian cycle. Ore's theorem relaxes this to: deg(u) + deg(v) ≥ n for every non-adjacent pair. Both are sufficient conditions only. A graph that fails them may still be Hamiltonian, so they can confirm existence but never rule it out.
• Necessary conditions. The graph must be connected, with at most two vertices of degree 1. These are fast ways to say no, never to say yes.

The knight's tour is a warning about heuristics: Warnsdorff's rule often finds tours with little backtracking, but it can fail depending on tie-breaking. Use it to order a correct search, not to replace one, as with the ordering heuristics in graph colouring.

Choosing a method

For the TSP route, a tour of cost exactly n means a Hamiltonian cycle exists; for a path, add the universal vertex described earlier. Only an exact solver can prove that no such tour exists.

Failure modes

• Solving the wrong variant. Path and cycle code agree on dense graphs and diverge on sparse ones. Name the variant in the function.
• Recursion depth. CPython's default recursion limit is 1000, so a long path raises RecursionError. Use an explicit stack for big inputs.
• No time limit. A no-instance can take exponentially long. Production code needs a budget and a third answer, unknown, which callers must handle.
• Unverified output. A bug that returns a near-path (a repeated vertex or a missing edge) is easy to write and easy to miss. Verify every result in O(n).

Trade-offs

Backtracking versus DP. Backtracking uses memory linear in n and can be extremely fast on structured inputs, but its running time is unpredictable and worst on the no-instances you most want to rule out. The DP's running time is fixed for a given n, whatever the graph, and the table caps n firmly.

Pruning cost versus tree size. A full reachability check at every node costs O(V + E). On dense graphs, where paths rarely get cut off, that can cost more than it saves. Measure on your inputs, and consider checking only every few levels.

What to do next

1. Write down your exact variant: path or cycle, directed or undirected, free or fixed endpoints.
2. Run the cheap checks first: connectivity, count of degree-1 vertices, DAG or tournament structure, Dirac or Ore.
3. Implement the subset DP for n up to about 20 and use it as a reference oracle in tests.
4. Implement pruned backtracking with reachability, dead-end counting, low-degree starts and Warnsdorff ordering.
5. Cross-check both on a few hundred random small graphs and verify every returned path edge by edge.
6. Measure node counts on graphs that look like your real inputs, especially no-instances.
7. Add a time budget and an explicit unknown result, and switch to an explicit stack before inputs reach the recursion limit.
8. For large inputs that must be decided, encode the problem for a SAT solver or reduce it to TSP instead of growing a custom search.