CoreSource checked

Held-Karp TSP

Solves exact TSP by dynamic programming over visited-city subsets and the current last city.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Optimization
Difficulty: Intermediate
Family: Dynamic Programming
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Held-Karp fixes a start city and stores the cheapest path that visits a subset of cities and ends at a chosen last city, then adds the closing edge back to the start.

Core Concepts

TSPsubset dynamic programmingbitmask stateexact exponential algorithmtour reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(2^n)

Worst

O(2^n)

Space

O(2^n)

When to Use

Use when exact TSP optimality matters and the number of cities is small.
Use when O(n^2 * 2^n) time and O(n * 2^n) memory fit the environment.

When Not to Use

Avoid for large TSP instances; memory grows exponentially with the number of cities.
Avoid when a metric approximation or local-search heuristic is sufficient.

What It Does

Computes the exact minimum TSP tour cost for small complete weighted graphs.
Uses subset dynamic programming to reuse optimal partial paths.
Records the last city so each state can be extended to an unvisited city.

Use Cases

Small exact TSP instances where exponential time and memory are acceptable.
Evaluating approximate TSP heuristics on small inputs.
Teaching bitmask dynamic programming on subsets.

Inputs

Objective, constraints, and candidate variables
Problem-specific costs or feasibility rules

Outputs

Best known feasible solution
Optimality or approximation result when available

Key Formulas (1)

Held-Karp recurrence

dp_[S]_[j] = min(dp_{[S − {j}]}_[i] + dist(i,j)) for i in S

dp[S][j] = min(dp[S - {j}][i] + dist(i,j)) for i in S

Builds the cheapest partial tour ending at city j after visiting subset S.

Pseudocode

1.Choose a fixed start city s
2.Set dp[{s}][s] = 0 and all other states to infinity
3.For each subset S that contains s
4.For each last city j in S
5.For each unvisited city k, relax dp[S union {k}][k]
6.Return min over last cities j of dp[allCities][j] + dist[j][s]

Canonical Example

Input: cities A, B, C, D on a unit square with diagonal distances sqrt(2)
Output: tour A->B->C->D->A with cost 4
Explanation: The DP compares every subset endpoint; the perimeter cycle beats tours that use two diagonals.

Implementation Notes

Fix one start city to remove rotational symmetry.
Store dp[subset][last] as the cheapest path from start through subset ending at last.
Iterate subsets by size, and reconstruct the route only if parent choices were stored.

Common Pitfalls

The subset mask must include the fixed start city and agree with city indexes.
Forgetting the closing edge from the last city to the start returns a path, not a tour.
Storing parent pointers for reconstruction can double already-large memory use.