Graph Algorithms8 min read

Hamiltonian Path

Visit every house exactly once — far harder than every bridge
brute force:Brutal · \(O(n!)\)bitmask DP:Exponential · \(O(2^n · n^2)\)NP status:NP-complete

A delivery driver needs to visit every house in a neighborhood exactly once. Easy to describe — but finding the best route is one of the hardest problems in all of computer science.

A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian circuit does the same and returns home. Unlike Eulerian paths (which visit every edge), there's no simple degree-check trick for Hamiltonian paths. You essentially have to try.

Why It's So Much Harder than Eulerian

Eulerian path: "visit every bridge once" → solvable in \(O(V+E)\) with a simple degree condition.

Hamiltonian path: "visit every house once" → NP-complete. No polynomial-time algorithm is known. No simple rule tells you whether one exists. The two problems sound almost the same, yet they're worlds apart in difficulty.

Brute Force: Try Every Route

The most obvious approach: try all possible orderings of the vertices. There are n! orderings — 10 vertices gives 3,628,800 routes to check. 20 vertices: 2.4 × 10^18. Completely infeasible beyond about 12 vertices.

Bitmask DP: The Held-Karp Trick

We can do much better with dynamic programming. The key observation: it doesn't matter how you visited a subset of vertices — only which subset you visited and where you are now matters for future decisions.

Define dp[mask][v] = true if there exists a valid path visiting exactly the vertices in mask and ending at vertex v. A bitmask encodes the subset compactly — bit i is 1 if vertex i has been visited.

Base case: dp[1 << v][v] = true for each starting vertex v.

Transition: dp[mask][v] = true if there exists a vertex u in mask (u ≠ v) such that dp[mask without v][u] = true and edge (u→v) exists.

Answer: a Hamiltonian path exists if dp[(1<<n)-1][v] is true for any v.

This runs in \(O(2^n · n^2)\) — still exponential, but the difference between \(O(n!)\) and \(O(2^n · n^2)\) is enormous. For n=20: 20! ≈ 2.4×10^18 vs 2^20 × 400 ≈ 4×10^8. The DP is about a billion times faster.

TSP: Add Edge Weights

The Travelling Salesman Problem extends Hamiltonian circuit with costs: find the minimum-cost circuit. Same DP works — store the minimum cost instead of a boolean. Same \(O(2^n · n^2)\) complexity, same NP-hardness.

For large n, approximation algorithms step in. For metric TSP (distances obey triangle inequality), the Christofides algorithm guarantees a solution at most 50% above optimal (3/2-approximation). A simple 2-approximation uses an MST: double all edges to create an Eulerian multigraph, find the circuit, then shortcut repeated vertices.

Note: The gap between Eulerian and Hamiltonian is a famous lesson in CS: problems that sound almost identical can be astronomically different in difficulty. One is \(O(V+E)\); the other might take the lifetime of the universe to solve exactly.

Hamiltonian Path — Bitmask DP

def hamiltonian_path(n, edges):
    adj = [[False]*n for _ in range(n)]
    for u, v in edges:
        adj[u][v] = True


    # dp[mask][v] = True if a path visiting mask ends at v
    dp = [[False]*n for _ in range(1<<n)]
    for v in range(n):
        dp[1<<v][v] = True


    for mask in range(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  # already visited
                if adj[v][u]:
                    dp[mask|(1<<u)][u] = True


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


# Path exists: 0->1->2->3
edges = [(0,1),(1,2),(2,3)]
print(hamiltonian_path(4, edges))  # True


# No path: 0->1, 0->2, but 3 is isolated
edges2 = [(0,1),(0,2)]
print(hamiltonian_path(4, edges2)) # False
Output
True
False

Complexity

💥 Brute force (all permutations)
20! ≈ 2.4×10^18 — if you checked one billion routes per second, this would take 75 years
Factorial — unusable beyond n≈12 \(O(n!)\)
⚡ Bitmask DP (Held-Karp)
2^20 × 400 ≈ 4×10^8 — feasible in seconds; uses \(O(2^n · n)\) memory
Exponential but tractable to n≈20 \(O(2^n · n^2)\)
🏷️ NP-complete status
A polynomial solution would prove P=NP — one of the greatest open problems in math
No known polynomial algorithm NP-complete
📏 TSP metric approximation
Christofides gives ≤ 1.5× optimal cost; simple MST-doubling gives ≤ 2×
Fast, near-optimal \(O(E \log E)\)

Quick check

A delivery app has 15 stops. Why is brute force completely impractical?

Continue reading