Traveling Salesman Problem — Held-Karp DP

The Problem — Finding the Shortest Hamiltonian Cycle

The Traveling Salesman Problem (TSP) asks: given N cities and the distance between each pair, find the shortest route that visits every city exactly once and returns to the start. It sounds deceptively simple, but it is one of the most famous NP-hard problems in computer science. The question it raises is fundamental: how do you explore a huge search space (N! permutations) without checking every single one?

The bitmask DP approach answers that question by trading exponential time for exponential space, keeping only the relevant subproblems. Instead of exploring all N! permutations blindly, you build up solutions systematically: for each subset of cities (represented as a bitmask) and each endpoint city, you track the minimum cost to visit all cities in that subset and end at that endpoint. This insight reduces the problem from O(N!) to O(2^N × N^2)—still exponential, but practical for N ≤ 20.

Why Brute Force Fails

A naive approach tries all N! permutations: start at city 0, visit cities 1 through N-1 in every possible order, then return to 0. For N = 10, that is 10! = 3.6 million permutations. For N = 20, it is 20! ≈ 2.4 × 10^18—impossible to enumerate in any reasonable time.

The scaling is catastrophic because the number of permutations grows as a factorial. Each additional city multiplies the work by one more factor. Even with a computer that checks one billion permutations per second, N = 20 would take millions of years.

Brute force also ignores the structure of the problem: many permutations visit the same set of cities in different orders, and the optimal path to visit a subset should be reused, not recalculated. This is where dynamic programming shines. Instead of enumerating permutations, you break the problem into smaller subproblems and build up the solution incrementally.

State Definition

The DP state is the heart of the algorithm. Define dp[mask][i] as the minimum cost to visit all cities represented by the bitmask and end at city i.

A bitmask is an integer where bit j is set to 1 if city j is included in the subset, and 0 otherwise. For example, with 5 cities (numbered 0–4), the bitmask 01011 (binary) = 11 (decimal) represents cities 0, 1, and 3.

The array dp has dimensions 2^N × N. With N = 20, this is 2^20 × 20 ≈ 20 million entries—feasible in memory, whereas 20! permutations is not.

Initialization — Base Cases

Start by initializing the base case: a single city (subset of size 1). To visit only city i, starting and ending at city i, the cost is 0—no travel required.

In bitmask form, the subset containing only city j is represented as 1 << j (bit j set, all others clear). So initialize:

dp[1 << i][i] = 0   # cost to visit only city i, ending at i, is 0

All other states start with infinity (or a large sentinel value), indicating they have not yet been computed. This is crucial: if you try to use a state that was never set, the algorithm will correctly reject it because the cost is infinite.

Transition — Building Larger Subsets

Now, build up from smaller subsets to larger ones. For each mask (subset), and for each endpoint city i in that subset, consider all possible previous cities j that were the second-to-last stop.

The recurrence relation is: to visit all cities in mask and end at i, you must have visited all cities in mask ^ (1 << i) (mask with bit i removed) and ended at some other city j. From j, you travel to i, paying dist[j][i] cost. The total cost is dp[mask ^ (1 << i)][j] + dist[j][i].

Try all possible previous cities j and take the minimum:

for mask in range(1, 1 << n):
  for i in range(n):
    if (mask & (1 << i)) == 0:
      continue  # city i not in this subset
    for j in range(n):
      if j == i or (mask & (1 << j)) == 0:
        continue  # j is the same as i, or j is not in the subset
      dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i])

This triple-nested loop processes all masks in increasing order of popcount (number of set bits). Crucially, when processing mask, the state mask ^ (1 << i) has one fewer set bit, so it has already been computed.

Finding the Answer

Once all subsets have been processed, the final answer is the minimum cost to visit all N cities and return to city 0.

The bitmask for all N cities is (1 << n) - 1. You want to visit all cities (any endpoint) and then return home. For each endpoint i, the cost is dp[(1 << n) - 1][i] + dist[i][0]. Take the minimum:

full_mask = (1 << n) - 1
answer = min(dp[full_mask][i] + dist[i][0] for i in range(n))

This sum accounts for the cost to visit all cities (stored in dp) and the cost of the final edge back to the starting city (the distance from endpoint i to city 0).

Time and Space Complexity

Time Complexity: O(2^N × N^2). The outer loop iterates over 2^N masks. For each mask, you loop over N cities i, and for each i, you loop over N cities j. The innermost operation (an addition and comparison) is O(1). Total: 2^N × N × N = O(2^N × N^2).

For N = 20, this is 2^20 × 20^2 ≈ 420 million operations—entirely feasible on a modern CPU. For N = 25, it is 2^25 × 625 ≈ 21 billion operations, still doable but starting to strain. For N = 30, it becomes impractical.

Space Complexity: O(2^N × N). The DP table has 2^N rows and N columns. For N = 20, this is about 20 million integers. At 4 bytes per integer, that is roughly 80 MB—well within typical RAM. For N = 25, it is 2.6 GB, which is still manageable.

The space constraint becomes the limiting factor before time does. For N = 20, memory is practical. For N = 24 or 25, it is tight. For N = 26+, you run out of RAM.

Worked Example — Small Instance

Consider 4 cities (0, 1, 2, 3) with distances:

Initialize single-city subsets: dp[0001][0] = dp[0010][1] = dp[0100][2] = dp[1000][3] = 0.

Process two-city subsets. For example, dp[0011][1] (visit cities 0 and 1, end at 1): the only previous city is 0, so dp[0011][1] = dp[0001][0] + dist[0][1] = 0 + 10 = 10.

Continue building up through three-city, then four-city subsets. The final answer is the minimum of dp[1111][i] + dist[i][0] for i = 0, 1, 2, 3. For this example, the optimal tour might be 0 → 1 → 3 → 2 → 0 with cost 10 + 25 + 30 + 15 = 80.

Optimizations and Variants

Space optimization: If you only care about the final answer (not reconstructing the tour), you can sometimes save memory by processing masks in a specific order. However, the core algorithm's space requirement remains O(2^N × N).

Path reconstruction: To recover the actual tour (not just the cost), store a parent pointer or previous-city pointer alongside each DP state. When building the final DP value, record which j was chosen as the best predecessor. After computing the final answer, backtrack through these pointers to reconstruct the tour.

Pruning: If you have a good lower bound (e.g., from the Held-Karp bound or a greedy heuristic), you can prune branches where the partial cost exceeds the bound. This heuristic improvement is less impactful than the DP itself, but it can help in practice.

Symmetric TSP optimization: If distances are symmetric (dist[i][j] = dist[j][i]), you can break symmetry by fixing city 0 as the starting point. This reduces the problem size slightly but does not change the asymptotic complexity.

Limitations and When to Use Alternatives

The bitmask DP approach is exact and optimal, but it is only practical for N ≤ 20–25. Beyond that, the exponential wall becomes insurmountable.

For larger N: switch to approximation algorithms. A greedy nearest-neighbor heuristic runs in O(N^2) and gives a solution within a factor of log(N) of optimal in expectation. Christofides' algorithm (O(N^3)) guarantees 1.5-approximation for metric TSP. Local search methods like 2-opt or simulated annealing improve a greedy solution iteratively without guarantees, but often perform well in practice.

For structured instances: if the cities lie in the plane and distances are Euclidean, specialized algorithms (e.g., Concorde TSP) can solve instances with tens of thousands of cities, far beyond what generic DP can handle. These leverage geometric properties that the general DP does not.

For asymmetric TSP: the bitmask DP works identically; there is no simplification. The algorithm does not depend on symmetry.

Real-World Applications

TSP appears in routing (delivery trucks visiting multiple stops), logistics (optimizing warehouse picking paths), machine learning (ordering data points to minimize cache misses), and circuit design (minimizing wire lengths on PCBs). In production, small instances (N ≤ 20) use exact DP or branch-and-bound; large instances (N ≥ 100) use heuristics or approximations.

The problem is also a teaching tool: it exemplifies the gap between NP-hard theory and practical algorithms, the value of DP in reducing exponential problems to (still exponential, but much more efficient) polynomial-table lookups, and the trade-off between exactness and scalability.