SpaceComplexity

What Is the Hamiltonian Path Problem? The Graph Challenge That Beats Computers

June 6, 20268 min read
dsaalgorithmsinterview-prepgraphs
What Is the Hamiltonian Path Problem? The Graph Challenge That Beats Computers
TL;DR
  • The hamiltonian path problem asks for a route through a graph that visits every vertex exactly once — no repeats, no skips
  • The decision version is NP-complete: no polynomial-time algorithm exists, and P=NP would need to be solved to find one
  • Backtracking is the standard approach — place vertices one by one and prune dead ends, worst-case O(n!)
  • The Held-Karp bitmask DP cuts this to O(n² · 2^n), making it tractable for n ≤ 20
  • Constraint n ≤ 12–20 is the interview signal — small bounds tell you exponential is expected
  • LeetCode Unique Paths III (980) and Shortest Path Visiting All Nodes (847) are disguised hamiltonian path problems
  • Hamiltonian vs. Eulerian: Eulerian paths have a clean O(E) algorithm; hamiltonian paths have no known fast solution

There's a problem so simple to state that you could explain it to a child, and so hard to solve that nobody has cracked it in polynomial time. Ever. A graph. Some vertices. Visit each one exactly once. Done.

That constraint, "each vertex exactly once," turns a trivial-sounding requirement into one of the most famous unsolved computational problems in existence. It's NP-complete. It shows up in coding interviews disguised as grid puzzles with suspiciously small constraints. And understanding it makes a whole category of interview problems click into place.

Hamilton Invented It as a Board Game in 1857

William Rowan Hamilton, the Irish mathematician who gave us quaternions, introduced the concept in 1857 as the Icosian Game. The puzzle was a wooden dodecahedron with 20 vertices (one for each major city) and asked players to find a route that visited every city exactly once and returned to the start.

That return-to-start variant is a Hamiltonian cycle. A Hamiltonian path is the relaxed version: visit every vertex once, end wherever you end up. Both are hard. Hamilton sold the rights to a game manufacturer for 25 pounds. The manufacturer lost money on it. The problem got the last laugh.

The formal definition:

A Hamiltonian path in a graph G is a path that visits each vertex of G exactly once. A Hamiltonian cycle is a Hamiltonian path where the last vertex is adjacent to the first.

Neither requires visiting every edge. That's the other problem entirely.

Hamiltonian vs. Eulerian: The Most Common Mix-Up

The two paths are easy to confuse because they sound similar. They are nothing alike in difficulty.

Hamiltonian path (NP-complete, visits every vertex once) vs. Eulerian path (O(E), traverses every edge once) shown on two equivalent graphs

Hamiltonian PathEulerian Path
VisitsEvery vertex onceEvery edge once
Named afterWilliam Rowan Hamilton (1857)Leonhard Euler (1736)
Decision problemNP-completePolynomial time
AlgorithmNo known poly-timeHierholzer's, O(E)
Condition to existUnknown in generalExactly 0 or 2 odd-degree vertices

Euler solved his path problem in 1736 by proving a clean structural condition. You can check whether an Eulerian path exists in O(V + E) and find it in O(E). The whole thing runs in linear time.

Hamiltonian paths have no such condition. There is no known fast algorithm, and none is expected: the problem is NP-complete. If you could solve it in polynomial time, you could solve every problem in NP, and the Clay Mathematics Institute would owe you a million dollars. Nobody has collected.

Richard Karp formalized this in 1972, showing Hamiltonian Cycle is one of 21 fundamental NP-complete problems, all provably equivalent in hardness.

Why There's No Shortcut

The core issue is that there's no local property you can check. You can look at a vertex's degree, its neighbors, its position in the graph, and none of it tells you whether a valid path runs through it.

This forces you to search. In the worst case, you have to try all possible orderings of the vertices. That's n! orderings for n vertices: 3.6 million for n = 10, and 2.4 × 10^18 for n = 20. For perspective, there are roughly 10^18 grains of sand on all of Earth's beaches. You'll be trying more orderings than there are sand grains. Your laptop will not be pleased.

Backtracking cuts the search tree early but doesn't change the worst case. You place vertices one by one, backtrack when no valid extension exists, and hope that pruning eliminates most branches. In the worst case you still touch every leaf.

def hamiltonian_path(graph: list[list[int]], n: int) -> list[int] | None:
    path = [0]
    visited = [False] * n
    visited[0] = True

    def backtrack() -> bool:
        if len(path) == n:
            return True
        current = path[-1]
        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                path.append(neighbor)
                if backtrack():
                    return True
                path.pop()
                visited[neighbor] = False
        return False

    if backtrack():
        return path
    return None

Time: O(n!) worst case. Space: O(n) for the recursion stack and visited array.

The Held-Karp Algorithm: O(n² · 2^n)

For small graphs, there's a smarter approach using bitmask dynamic programming. The Held-Karp algorithm, developed in 1962, was built to solve the Traveling Salesman Problem and adapts cleanly to check for any Hamiltonian path.

The state is dp[mask][v]: can you visit exactly the vertices in mask, ending at vertex v?

def hamiltonian_path_dp(adj: list[list[bool]], n: int) -> bool:
    dp = [[False] * n for _ in range(1 << n)]

    for v in range(n):
        dp[1 << v][v] = True

    for mask in range(1, 1 << n):
        for v in range(n):
            if not dp[mask][v]:
                continue
            if not (mask >> v & 1):
                continue
            for u in range(n):
                if mask >> u & 1:
                    continue
                if adj[v][u]:
                    dp[mask | (1 << u)][u] = True

    full_mask = (1 << n) - 1
    return any(dp[full_mask][v] for v in range(n))

Time: O(n² · 2^n). Space: O(n · 2^n).

This is dramatically better than O(n!) for small n. For n = 20, that's roughly 20 million operations instead of 2.4 × 10^18. Still exponential, but tractable when the input is small, which is exactly the constraint you'll see in interview problems.

Where This Shows Up in Interviews

Interviewers rarely say "find a Hamiltonian path." They disguise it. The tells are a graph or grid, a requirement to visit every cell or node exactly once, and a constraint on n small enough that exponential solutions pass.

LeetCode 980: Unique Paths III. You're given a grid where some cells are empty, one is the start, and one is the end. Count paths from start to end that visit every empty cell exactly once. This is counting Hamiltonian paths on a grid graph. The intended solution is DFS backtracking. The constraint caps the grid at 20 non-obstacle cells, which is the tell.

LeetCode 847: Shortest Path Visiting All Nodes. An undirected graph with n nodes (n ≤ 12). Find the shortest path visiting every node at least once. The "at least once" relaxation means it isn't a strict Hamiltonian path, but the bitmask DP solution with states (node, visited_mask) is the same structure as Held-Karp. The small n is the tell.

The Knight's Tour. Can a knight visit every square on an 8×8 chessboard exactly once? It's a Hamiltonian path problem on the graph where vertices are squares and edges are legal knight moves. Euler studied it in 1759. Backtracking with Warnsdorff's heuristic (always move to the neighbor with the fewest onward moves) finds tours efficiently in practice, even without a worst-case guarantee.

Groot from Guardians of the Galaxy looking blank and lost, with the caption: "My face when the interviewer asks me what sync.Pool is actually doing internally in Go and how does it interact with the garbage collector but all I know is how to reverse a linked list"

When the grid problem says "visit every empty cell exactly once" and you realize you're not doing a simple DFS.

The Constraint Block Tells You Which Algorithm to Use

When you see a "visit every node/cell exactly once" requirement, read the constraint on n before writing a single line of code.

  • n ≤ 12: bitmask DP almost certainly intended, O(n² · 2^n) fits comfortably
  • n ≤ 20: bitmask DP still feasible, maybe tight
  • n ≤ small constant on a grid: backtracking with pruning
  • n in the hundreds or thousands: re-read the problem. Something else is going on.

A small n constraint is the signal. Interviewers wouldn't bound n at 12 if the intended solution were O(n log n). The tight bound is telling you to go exponential, which tells you the structure is Hamiltonian. Work backwards from the constraint to the algorithm.

The Real World Doesn't Get to Cheat Either

Hamiltonian paths come up outside puzzles. Genome assembly in DNA sequencing constructs overlap graphs where the goal is a path through fragments that explains the full sequence. The Traveling Salesman Problem, which logistics companies spend millions solving approximately, is the optimization version of Hamiltonian cycle. Circuit board design asks for component orderings that minimize wire lengths, another TSP variant.

In all these cases the exact solution is intractable for large inputs. Practitioners use approximation algorithms, heuristics, and specialized solvers that work well without worst-case guarantees. The problem doesn't get easier when it's real. The stakes just get higher.

Practice It Under Pressure

Recognizing a Hamiltonian path problem in an interview is one thing. Deriving the bitmask DP from scratch while someone watches you is another. The gap between understanding and live execution is where most preparation falls short.

SpaceComplexity gives you voice-based mock interviews with rubric feedback across problem-solving, communication, and code quality. If you've been studying bitmask DP in silence, it's worth finding out whether you can actually walk an interviewer through it.

Further Reading