Held–Karp Traveling Salesman

Worked Example: Square Instance

Let's consider a symmetric square distance matrix for 4 cities:

[[0, 1, 2, 1], [1, 0, 1, 2], [2, 1, 0, 1], [1, 2, 1, 0]]

We trace the dynamic programming subsets starting from node 0:

1. Initialize dp[{0}][0] = 0. All other dp values are ∞.
2. For subsets of size 2 containing 0:
   • dp[{0, 1}][1] = dp[{0}][0] + dist[0][1] = 0 + 1 = 1
   • dp[{0, 2}][2] = dp[{0}][0] + dist[0][2] = 0 + 2 = 2
   • dp[{0, 3}][3] = dp[{0}][0] + dist[0][3] = 0 + 1 = 1
3. For subsets of size 3 containing 0:
   • dp[{0, 1, 2}][2] = min(dp[{0, 1}][1] + dist[1][2]) = 1 + 1 = 2
   • dp[{0, 1, 3}][3] = min(dp[{0, 1}][1] + dist[1][3]) = 1 + 2 = 3
   • dp[{0, 2, 3}][3] = min(dp[{0, 2}][2] + dist[2][3]) = 2 + 1 = 3
4. For subsets of size 4 containing 0:
   • dp[{0, 1, 2, 3}][3] = min(dp[{0, 1, 2}][2] + dist[2][3], dp[{0, 1, 3}][1] + dist[1][3]) = 2 + 1 = 3
5. Finally, completing the tour back to 0:
   • min(dp[{0, 1, 2, 3}][3] + dist[3][0]) = 3 + 1 = 4.

The optimal cost is 4, with the path 0 → 1 → 2 → 3 → 0.

Experiment

You can interactively explore different instances:

1. Open the Held-Karp module.
2. Observe the optimal tour and cost for the default Square instance.
3. Change the Instance to Asymmetric. Notice how the distances depend on the direction.
4. Change to Disconnected to see what happens when no Hamiltonian tour is possible. The cost will be Unavailable.

Limitations

While much faster than brute force O(n!), the Held-Karp algorithm's O(n² 2ⁿ) time and space complexity means it is practical only for small graphs (typically up to n = 20). For larger graphs, approximation algorithms or heuristics such as 2-opt or the Christofides algorithm are necessary. Additionally, if the graph is disconnected or missing crucial edges, an exact finite answer will not exist.

References

The concepts are founded upon earlier works:

• A Dynamic Programming Approach to Sequencing Problems - The original paper by Michael Held and Richard M. Karp (1962).