Hamiltonian Path

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle returns to the start. Deciding existence is NP-complete — in sharp contrast to Eulerian paths, which are linear-time.

The difference is instructive: “use every edge once” has a clean local characterisation (degree parity); “use every vertex once” has none.

Exact algorithms

Bitmask DP — $O(2^n{n}^2)$

The standard approach for $n\le 20$-$22$.

// dp[mask][v] = can we visit exactly `mask` ending at v?
bool hamiltonianPath(int n, vector<vector<bool>>& adjm) {
    vector<vector<bool>> dp(1 << n, vector<bool>(n, false));
    for (int v = 0; v < n; v++) dp[1 << v][v] = true;
    for (int mask = 1; mask < (1 << n); mask++)
        for (int v = 0; v < n; v++) {
            if (!dp[mask][v]) continue;
            for (int u = 0; u < n; u++)
                if (!(mask >> u & 1) && adjm[v][u]) dp[mask | (1 << u)][u] = true;
        }
    for (int v = 0; v < n; v++) if (dp[(1 << n) - 1][v]) return true;
    return false;
}

Weighted, this is Held-Karp and solves TSP.

Counting, not just deciding

The inclusion-exclusion formula counts Hamiltonian paths in $O(2^n{n}^2)$ time and $O(n^2)$ space (versus $O(2^{n}n)$ for the DP):

$\#\text{Ham paths}={\sum }_{S\subseteq V}(-1{)}^{|V\setminus S|}(\text{number of walks of length }n-1\text{ using only }S).$

Walks are counted by a matrix power, so the memory is tiny. When $n\approx 22$ and the DP’s memory does not fit, this is the fallback.

Sufficient conditions (for existence)

None of these are necessary, but each is easy to check:

Theorem	Condition
Dirac	every vertex has $\mathrm{deg}\ge n/2$ ⟹ Hamiltonian cycle ($n\ge 3$)
Ore	$\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$ for every non-adjacent pair ⟹ Hamiltonian cycle
Bondy-Chvátal	closure argument: repeatedly join non-adjacent pairs with $\mathrm{deg}$ sum $\ge n$; $G$ is Hamiltonian iff its closure is
Tournaments	every tournament has a Hamiltonian path (constructive: insertion sort on the vertices!)
Chvátal-Erdős	connectivity $\ge$ independence number ⟹ Hamiltonian

The tournament result is genuinely useful: in a tournament, a Hamiltonian path can be built in $O(n\log n)$ by inserting vertices one at a time into a growing path — literally insertion sort with “beats” as the comparison. A strongly connected tournament even has a Hamiltonian cycle.

Special graph classes

Class	Hamiltonicity
Complete graph	trivially yes
Tournament	Hamiltonian path always exists
Grid graph	polynomial-time decidable (Itai-Papadimitriou-Szwarcfiter)
Interval graph	polynomial
Bipartite with $|L|\ne |R|$	no Hamiltonian cycle
Graph with a cut vertex	no Hamiltonian cycle
Tree	Hamiltonian path iff it is a path
Cubic planar	still NP-complete

The bipartite parity check and the cut-vertex check are cheap necessary conditions worth applying before any expensive search.

Practical search

For $n$ beyond the DP range, use branch and bound with strong pruning:

• prune when a vertex of degree 0 remains in the unvisited set;
• prune when the remaining graph becomes disconnected;
• prune when two or more unvisited vertices have degree 1 in the remaining graph;
• order candidates by fewest remaining options (Warnsdorff’s rule — this is what makes knight’s tours solvable on large boards almost instantly).

See also: Travelling Salesman · Held-Karp · Eulerian Path