xvii. Hamiltonian Paths and TSP

Visiting every vertex once is NP-complete (unlike edges, Euler Tours). Exact tools: Held–Karp bitmask DP in $O(2^n{n}^2)$ (or $O(2^{n}n)$ for the decision version with bitsets), inclusion–exclusion counting in polynomial space, and branch and bound. Polynomial special cases: tournaments always have a Hamiltonian path; Dirac/Ore degree conditions guarantee cycles; bitonic tours are $O(n^2)$. Metric TSP has approximations (2 via MST doubling, 3/2 Christofides); marathon-style instances use 2-opt/Or-opt local search (Heuristics).

Held–Karp

pair<ll, vector<int>> tsp(const vector<vector<ll>>& w) {     // minimum Hamiltonian cycle through 0, and the tour
    int n = sz(w); const ll INF = LLONG_MAX / 4;
    if (n == 1) return {0, {0}};
    vector<vector<ll>> dp(1 << n, vector<ll>(n, INF)); dp[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask += 2) for (int i = 0; i < n; i++) {
        if (dp[mask][i] >= INF) continue;
        for (int j = 0; j < n; j++) if (!(mask >> j & 1)) dp[mask | 1 << j][j] = min(dp[mask | 1 << j][j], dp[mask][i] + w[i][j]);
    }
    int full = (1 << n) - 1, last = -1; ll best = INF;
    for (int i = 1; i < n; i++) if (dp[full][i] + w[i][0] < best) best = dp[full][i] + w[i][0], last = i;
    vector<int> tour; int mask = full, cur = last;                  // walk back by re-deriving predecessors
    while (cur != 0) {
        tour.push_back(cur); int pm = mask ^ 1 << cur, prev = 0;
        for (int j = 0; j < n; j++) if ((pm >> j & 1) && dp[pm][j] < INF && dp[pm][j] + w[j][cur] == dp[mask][cur]) { prev = j; break; }
        mask = pm; cur = prev;
    }
    tour.push_back(0); reverse(all(tour));
    return {best, tour};
}

Memory is the binding constraint: $2^{20}\cdot 20$ values of 8 bytes is 168 MB. Store 32-bit costs, or only the masks containing vertex 0 (half), or iterate by popcount layers.

$n$	states $\times$ transitions	memory (8-byte cells)
15	$7.4\cdot 10^6$	4 MB
18	$8.5\cdot 10^7$	38 MB
20	$4.2\cdot 10^8$	168 MB — tight
22	$2.0\cdot 10^9$	738 MB — usually too much

Decision version in $O(2^{n}n)$: let ends[mask] be the bitmask of vertices $v$ such that some Hamiltonian path of mask ends at $v$; then $v\in \text{ends}[\text{mask}]$ iff $\text{ends}[\text{mask}\setminus v]\&\text{adj}[v]\ne 0$.

bool hamiltonianPath(const vector<int>& adj) {               // adj[v] = neighbour bitmask, n <= ~25
    int n = sz(adj); vector<int> ends(1 << n);
    for (int v = 0; v < n; v++) ends[1 << v] = 1 << v;
    for (int mask = 1; mask < (1 << n); mask++) for (int v = 0; v < n; v++)
        if ((mask >> v & 1) && mask != (1 << v) && (ends[mask ^ 1 << v] & adj[v])) ends[mask] |= 1 << v;
    return ends[(1 << n) - 1] != 0;
}

Proof: Held–Karp optimal substructure

A minimum-cost path from $0$ through exactly the set mask ending at $i$ consists of a path through $\text{mask}\setminus \{i\}$ ending at some $j$, plus the edge $(j,i)$; that prefix must itself be optimal for $(\text{mask}\setminus \{i\},j)$, otherwise replacing it lowers the cost. By induction on $|\text{mask}|$ the push-style DP computes these optima. The decision version is the same recurrence over the Boolean semiring, with the inner loop over $j$ replaced by one AND of bitmasks.

Counting Hamiltonian paths/cycles in polynomial space

Inclusion–exclusion over the set of vertices allowed: the number of Hamiltonian paths equals ${\sum }_{S\subseteq V}(-1{)}^{n-|S|}{W}_{n-1}(S)$, where $W_{n-1}(S)$ is the number of walks with $n-1$ edges using only vertices of $S$ (computed by a DP over walk length in $O(n\cdot m)$ per subset). $O(2^{n}nm)$ time, $O(n)$ extra memory.

ll countHamPaths(const vector<vector<int>>& g, ll p) {        // number of Hamiltonian paths (directed sequences) mod p
    int n = sz(g); ll res = 0;
    for (int S = 0; S < (1 << n); S++) {
        vector<ll> cur(n), nxt(n);
        for (int v = 0; v < n; v++) cur[v] = S >> v & 1;
        for (int step = 1; step < n; step++) {
            fill(all(nxt), 0);
            for (int u = 0; u < n; u++) if (cur[u]) for (int v : g[u]) if (S >> v & 1) nxt[v] = (nxt[v] + cur[u]) % p;
            swap(cur, nxt);
        }
        ll walks = 0; for (ll x : cur) walks = (walks + x) % p;
        res = ((n - __builtin_popcount(S)) % 2 ? res - walks + p : res + walks) % p;
    }
    return res;
}

Proof: the inclusion–exclusion formula

A walk with $n-1$ edges has $n$ vertex occurrences. It is a Hamiltonian path iff it visits all $n$ vertices. For a walk with vertex set $U$, it is counted in $W(S)$ for every $S\supseteq U$, with total signed weight ${\sum }_{S\supseteq U}(-1{)}^{n-|S|}={\sum }_{k=0}^{n-|U|}(\genfrac{}{}{0ex}{}{n-|U|}{k})(-1{)}^{n-|U|-k}=[U=V]$. So exactly the walks visiting every vertex survive, and those are precisely Hamiltonian paths (each vertex once, since there are only $n$ occurrences).

Existence results

Result	Statement
Rédei	every tournament has a Hamiltonian path (insertion: binary search where to insert each new vertex)
Camion	a strongly connected tournament has a Hamiltonian cycle
Dirac	$n\ge 3$, $\min \mathrm{deg}\ge n/2$ ⟹ Hamiltonian cycle
Ore	$\mathrm{deg}u+\mathrm{deg}v\ge n$ for all non-adjacent $u,v$ ⟹ Hamiltonian cycle
Bondy–Chvátal	$G$ is Hamiltonian iff its closure (repeatedly join non-adjacent $u,v$ with $\mathrm{deg}u+\mathrm{deg}v\ge n$) is
necessary	no cut vertex (for a cycle); bipartite with unequal sides ⟹ no cycle; at most two degree-1 vertices (for a path)
grid graph	polynomial-time decidable (Itai–Papadimitriou–Szwarcfiter)
interval graph	polynomial
tree	Hamiltonian path iff the tree already is one
cubic planar	still NP-complete

The bipartite-parity and cut-vertex checks above are the cheapest necessary conditions — apply them before any expensive search.

vector<int> tournamentPath(int n, function<bool(int, int)> beats) {   // beats(u, v): edge u -> v
    vector<int> path;
    for (int v = 0; v < n; v++) {                           // insert v before the first vertex it beats, found by binary search
        int lo = 0, hi = sz(path);                         // invariant: path[lo-1] -> v (or lo = 0), v -> path[hi] (or hi = end)
        while (lo < hi) { int mid = (lo + hi) / 2; if (beats(path[mid], v)) lo = mid + 1; else hi = mid; }
        path.insert(path.begin() + lo, v);
    }
    return path;
}

Proof: tournament insertion and Ore's theorem

Tournament: the binary search maintains ”$\text{path}[lo-1]\to v$ (or $lo=0$) and $v\to \text{path}[hi]$ (or $hi=|\text{path}|$)”: if $\text{path}[mid]$ beats $v$, moving $lo$ to $mid+1$ keeps the left part, otherwise $v$ beats $\text{path}[mid]$ and $hi=mid$. When $lo=hi$, inserting $v$ at position $lo$ gives edges $\text{path}[lo-1]\to v\to \text{path}[lo]$, so the path remains Hamiltonian on the inserted vertices. $O(n\log n)$ queries (the vector insertion is $O(n)$ each but cheap).
Ore: suppose $G$ satisfies Ore’s condition but is not Hamiltonian; add edges while keeping it non-Hamiltonian until adding any missing edge creates a Hamiltonian cycle (the condition is preserved since degrees only grow). $G\ne K_n$, so take non-adjacent $u,v$: $G+uv$ has a Hamiltonian cycle through $uv$, so $G$ has a Hamiltonian path $u=x_1,\dots ,x_n=v$. If $u\sim x_{i+1}$ and $v\sim x_i$ for some $i$, then $x_1{x}_{i+1}\dots x_n{x}_i\dots x_1$ is a Hamiltonian cycle. Otherwise, for each of the $\mathrm{deg}u$ indices $i$ with $u\sim x_{i+1}$, $v\nsim x_i$, so $\mathrm{deg}v\le (n-1)-\mathrm{deg}u$, contradicting $\mathrm{deg}u+\mathrm{deg}v\ge n$. Dirac is the special case.

TSP beyond exact DP

Setting	Method	Guarantee
bitonic tours (points sorted by $x$, go right then return left)	$d{p}_{i,j}$ = best pair of paths ending at $i,j$, extend with $\max (i,j)+1$	exact, $O(n^2)$
metric	double the MST and shortcut	2
metric	Christofides (MST + min perfect matching on odd vertices)	3/2
Euclidean	Arora’s PTAS	$1+\epsilon$
general (no triangle inequality)	no constant approximation unless P = NP	—
marathon instances	nearest neighbour + 2-opt / Or-opt / Lin–Kernighan, simulated annealing	none, near-optimal in practice
$n\le 60$–$100$	branch and bound with 1-tree (Held–Karp Lagrangian) bounds	exact
bottleneck TSP	binary search on the threshold + Hamiltonicity test	exact if the test is

Proof: MST doubling and Christofides

Deleting one edge of an optimal tour leaves a spanning path, so $\text{MST}\le \text{OPT}$. Doubling the MST gives an Eulerian multigraph of weight $\le 2\text{OPT}$; shortcutting repeated vertices (triangle inequality) doesn’t increase the length. Christofides: the odd-degree vertices $O$ of the MST are even in number; the optimal tour shortcut to $O$ has length $\le \text{OPT}$ and splits into two perfect matchings on $O$, so the minimum perfect matching $M$ has weight $\le \text{OPT}/2$. $\text{MST}+M$ is Eulerian with weight $\le 1.5\text{OPT}$, and shortcutting gives the tour.

Branch and bound pruning

For plain Hamiltonian-path search beyond the bitmask range, strong pruning matters more than the search order:

• prune when an unvisited vertex has degree 0 in the remaining graph;
• prune when the remaining graph becomes disconnected;
• prune when two or more unvisited vertices have degree 1 (at most one can be the path’s other endpoint);
• order candidates by fewest remaining options first (Warnsdorff’s rule — the reason knight’s tours are solvable on large boards almost instantly).

For TSP branch and bound specifically, lower bounds in increasing strength:

1. sum of the two cheapest edges at each city, halved;
2. MST of the unvisited cities plus the two cheapest edges connecting it back to the visited path;
3. the Held–Karp 1-tree bound — a Lagrangian relaxation that iteratively adjusts per-vertex penalties, typically within 1% of optimal; this is a different “Held–Karp” from the exact DP above (same two authors, same paper, two different results — don’t confuse a bitmask-DP solver with a 1-tree-bound pruner when reading about either), and the reason Concorde solves enormous instances exactly.

Variants worth naming

Variant	Note
Path instead of cycle	drop the closing edge $w(i,0)$
Asymmetric TSP ($w(i,j)\ne w(j,i)$)	Held–Karp is unchanged; Christofides does not apply (needs the triangle inequality on a symmetric metric)
Bottleneck TSP	binary search the threshold + Hamiltonicity test
TSP with time windows	much harder in general; usually heuristic
Multiple salesmen (mTSP)	add $k-1$ copies of the depot
Vehicle routing (VRP)	TSP plus capacities — the industrial version
Steiner TSP	may skip non-required cities — Dreyfus–Wagner territory ([[21-complete-search/07-steiner-tree