Chapter 5 · Euler Tours and Hamilton Cycles
Held–Karp: Hamilton in O(2ⁿn²)
Exponential, but the right exponential — bitmask DP for Hamiltonian paths, cycles and the travelling salesman.
Deciding Hamiltonicity is NP-complete, so we settle for exponential — and the exact exponent is the whole sport. The classic is O(2n n2) time, O(2n n) memory, via "which subsets, ending where?".
dp[M][v] = "true ⇔ there is a path that visits exactly the vertices of M and ends at v, with v ∈ M". Transition: dp[M][v] = vee_{u ∈ M ∖ {v}, uv ∈ E} dp[M ∖ {v}][u]. Answer: veeu dp[V][u] ∧ (u ∼ s) for a cycle through a fixed start s; the path version is veeu,v dp[V][u] (any endpoints).
const int MAXN = 20;
bool dp[1 << MAXN][MAXN];
int main() {
int n, m; cin >> n >> m;
vector<int> adj(n); // bitmask of neighbours
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v; --u; --v;
adj[u] |= 1 << v; adj[v] |= 1 << u;
}
for (int s = 0; s < n; s++) dp[1 << s][s] = 1;
for (int M = 1; M < (1 << n); M++)
for (int v = 0; v < n; v++) if (dp[M][v] && (M >> v & 1)) {
int rest = adj[v] & ~M; // only unvisited neighbours
while (rest) {
int u = __builtin_ctz(rest); rest &= rest - 1;
dp[M | 1 << u][u] = 1;
}
}
int all = (1 << n) - 1;
for (int v = 0; v < n; v++)
if (dp[all][v] && (adj[v] & 1)) { cout << "YES\n"; return 0; }
cout << "NO\n";
}adj[v] & ~MIterating u over all n vertices costs 2n n2; iterating only over unvisited neighbours via ctz bit-extraction costs ∑M ∑v ∈ M degbar M(v), which is bounded by 2n m / 2 in the worst case but typically much smaller — and for dense graphs, the bit-OR form reach[M] |= ... reduces it to O(2n · n / 64) per step with a bitset.
#TSP, i.e. the weighted version
Same state, but keep the cost and take min: dp[M][v] = minu dp[M ∖ {v}][u] + w(u,v).
int dp[1 << 20][20]; // 4 * 10^6 ints: fits
for (int v = 1; v < n; v++) dp[1][v] = w(0, v); // start fixed at 0
for (int M = 1; M < 1 << (n-1); M++)
for (int v = 1; v < n; v++) if (M >> (v-1) & 1)
for (int u = 1; u < n; u++) if (!(M >> (u-1) & 1))
dp[M | 1 << (u-1)][u] = min(dp[M | 1 << (u-1)][u], dp[M][v] + w(v, u));
int ans = INF;
for (int v = 1; v < n; v++) ans = min(ans, dp[(1 << (n-1)) - 1][v] + w(v, 0));What the numbers really allow
- n ≤ 20: 220 · 400 ≈ 4 · 108 naive inner steps — tight, so use the bit tricks or drop to n ≤ 18;
- memory 2n · n: at n = 20 that is 4 × 106 cells = 16 MB for
int, 32 MB forlong long— check the limit before choosing the state, - n ≤ 25: meet in the middle on paths, or Held–Karp with
unordered-style pruning; - metric TSP: Christofides gives (3)/(2)-approx in poly time (MST + min-weight perfect matching on odd-degree vertices — which is why General Matching and Blossoms matters), and the path version is even a bit better; for general weights no 2-ε approximation exists unless P = NP.
Replace bool by long long mod M and vee by +. The count mod 2 is the interesting theoretical object (it relates to the determinant of the adjacency matrix over 𝔽2 — The Matrix–Tree Theorem has the parallel argument for spanning trees).
- Forgetting to fix a start vertex for the cycle version: then every cycle is counted n times (or 2n if you care about direction) and the boolean version stays correct but the count is wrong.
- Transition order: iterate masks by increasing popcount, or at least ensure M ∖ {v} < M numerically (true for bitmasks, so a plain increasing loop is fine — but do not "optimise" by iterating vertices in the outer loop unless you keep that invariant).
- Using dp[M][v] = "visits at least M". Half-open vs exact-subset semantics changes the answer.
Brute force is O(n!); Held–Karp is O(2n n2) — the improvement comes from memoising over subsets, i.e. realising that "which vertices are used and where am I" is all the future cares about. That single observation is the same one behind every "DP over bitmasks" problem (assignment, scheduling with conflicts, subset convolution warm-ups), and the way to recognise it is a constraint of the form "each item used at most once".