A Bit of History
The problem's earliest documented appearance is genuinely practical, not mathematical: an 1832 German handbook titled Der Handlungsreisende ("The Traveling Salesman"), written for actual traveling salesmen, casually described the value of planning an efficient round trip through a list of towns. Mathematicians formalized it a century later — Karl Menger (already met in Part 8 for his connectivity theorem) discussed it at a Vienna mathematical seminar around 1930, and Hassler Whitney (Part 11's Matrix-Tree contributor and Part 12's Dirac-theorem context) is credited with popularizing the "Traveling Salesman Problem" name in the mid-1930s. The watershed moment came in 1954, when George Dantzig, Delbert Ray Fulkerson (yes — the same Fulkerson of Ford-Fulkerson, an upcoming deep dive), and Selmer Johnson used linear programming to find and prove optimal a tour through 49 U.S. cities — a genuinely enormous computational achievement for the era, and the founding result of an entire subfield of operations research still active today.
TSP Fundamentals
Given a complete weighted graph, the Traveling Salesman Problem asks for the minimum-weight Hamiltonian cycle: leave a starting city, visit every other city exactly once, and return to the start while minimizing total cost. Part 12 asked only whether a Hamiltonian cycle exists. TSP adds a second layer: among all valid Hamiltonian cycles, which one is cheapest?
Hamiltonian Cycle asks “can I tour them all?” — TSP asks “which tour costs least?”
The same cities can have many valid Hamiltonian cycles. TSP compares their total weights. In a complete graph every pair of cities has a candidate edge, so the challenge is choosing the globally best combination of edges rather than merely finding connectivity.
Memory hook
Hamiltonian = visit every vertex. TSP = do that as cheaply as possible.
Variants matter. Symmetric TSP assumes \(w(u,v)=w(v,u)\); asymmetric TSP allows the two directions to have different costs, as with one-way streets. Metric TSP additionally assumes the triangle inequality, meaning direct travel never costs more than taking a detour.
Why the Triangle Inequality Changes Everything
Shortcutting is safe only when direct travel is no worse than a detour
Metric TSP satisfies \(w(A,C) \leq w(A,B)+w(B,C)\). That is why algorithms such as Christofides can take an Eulerian walk that revisits cities and then shortcut repeated visits without increasing total cost.
NP-Hard, Building on Part 12's Warning
TSP contains Hamiltonian Cycle as a special case. Given a graph on \(n\) vertices, make a complete weighted graph where every original edge costs 1 and every missing edge costs 2. The original graph has a Hamiltonian cycle exactly when the new TSP instance has a tour of total cost \(n\). So an efficient exact TSP solver would also efficiently solve Hamiltonian Cycle.
Exact Approaches
Exact algorithms promise the true optimum. The difficulty is the number of possibilities they must distinguish. Two useful mental models are: enumerate complete tours (brute force) or merge equivalent partial tours (Held–Karp).
Brute Force: Try Every Tour
Fix one city as the start, enumerate every ordering of the remaining cities, close the cycle, compute its weight, and keep the minimum. In symmetric TSP a tour and its reverse are equivalent, leaving \((n-1)!/2\) distinct tours.
Factorial growth turns “just one more city” into a huge jump
At 20 cities there are already about 60 quadrillion distinct symmetric tours. Adding one city multiplies that count by 20, pushing 21 cities above \(10^{18}\) possibilities.
Held–Karp Dynamic Programming: Remember the Set, Not the Whole History
Held–Karp notices that many partial tours are equivalent for the future. If two histories have visited the same set of cities and currently end at the same city, only the cheaper history matters.
Here \(S\) is the visited set (including the fixed start \(s\)) and \(v\) is the current endpoint. The base state is \(\operatorname{dp}[\{s\}][s]=0\); once all cities are included, add the final edge back to \(s\).
Different histories collapse into one “best cost for this state”
Exact does not mean “brute force only”
Modern exact solvers also use branch-and-bound, cutting planes, integer programming, and strong lower bounds. Held–Karp is especially valuable for learning because its state compression makes the exponential structure visible.
Heuristics & Approximation
For large instances, exact optimality may be too expensive. A heuristic aims for a good answer quickly but may have no worst-case quality guarantee. An approximation algorithm is different: it runs in polynomial time and comes with a theorem bounding how far its answer can be from optimal.
Nearest Neighbor: Locally Sensible, Globally Risky
Nearest neighbor repeatedly goes to the closest unvisited city. Every step looks reasonable, but TSP is a cycle: a cheap local decision can leave one awkward city for the end, forcing a very expensive closing edge.
Nearest neighbor optimizes the next edge, not the finished tour
2-opt: Repair a Tour by Rewiring Two Edges
2-opt starts with any complete tour and asks whether two edges can be removed and reconnected in the other way to shorten the tour. If yes, reverse the affected segment and keep the improvement. Repeat until no improving 2-edge exchange remains.
In Euclidean TSP, crossing edges are a visual clue that 2-opt can improve the tour
For general metric TSP, 2-opt is defined by cost improvement rather than geometry. In Euclidean instances, crossings make the idea especially intuitive.
Christofides' Algorithm (Preview)
A 3/2-Approximation, Built from Parts Already in This Series
For metric TSP, Christofides' algorithm guarantees a tour whose cost is at most \(\tfrac{3}{2}\) times optimum. It combines an MST, parity repair by minimum-weight perfect matching, an Eulerian circuit, and triangle-inequality shortcutting.
Christofides turns a cheap tree into an Eulerian walk, then shortcuts it into a TSP tour
The guarantee comes from two lower bounds: deleting one edge from any TSP tour leaves a spanning tree, so the MST costs at most OPT; the matching needed to repair the MST's odd degrees can be bounded by at most half of OPT. Before shortcutting, the combined cost is therefore at most \(\text{OPT}+\tfrac12\text{OPT}\).
How the approaches fit together
Brute force searches complete tours. Held–Karp compresses equivalent partial tours. Nearest neighbor builds one quick tour greedily. 2-opt improves a tour locally. Christofides sacrifices exactness but adds a rigorous global guarantee for metric TSP.
Exactness, speed, and guarantees are different axes
| Method | Core idea | Exact? | Typical guarantee / cost |
|---|---|---|---|
| Brute force | Enumerate tours | Yes | \(O(n!)\) |
| Held–Karp | Subset DP | Yes | \(O(n^2 2^n)\) |
| Nearest neighbor | Cheapest next city | No | Fast; no constant-factor guarantee in general |
| 2-opt | Local edge exchanges | No | Local optimum; often strong in practice |
| Christofides | MST + matching + Euler tour | No | At most \(3/2\) OPT for metric TSP |
Exercises
- Compute the number of distinct tours for \(n = 10\) cities using \((n-1)!/2\), and compare it to \(n^2 2^n\) from Held-Karp — at what \(n\) does Held-Karp's bound become the larger of the two?
- Run nearest-neighbor by hand on 5 cities arranged so that the greedy choice at the first step forces a very long final edge, demonstrating the heuristic's lack of a worst-case guarantee.
- Trace one 2-opt improvement step by hand on a small crossing tour (four cities where the naive tour's edges cross when drawn), showing how uncrossing the edges shortens the total distance.
- Challenge: Implement brute-force TSP for \(n \leq 10\) and Held-Karp's DP for the same instances, and verify they agree while measuring the dramatic runtime difference.
Conclusion & Next Steps
TSP is the canonical lesson in algorithmic trade-offs. Brute force exposes the factorial explosion; Held–Karp shows how dynamic programming compresses equivalent histories without giving up optimality; nearest neighbor and 2-opt show how useful heuristics can be without global guarantees; and Christofides demonstrates how approximation trades exactness for a theorem-backed quality bound. Next, we turn to network flow — another setting where local-looking operations combine into powerful global guarantees.
Next in the Series
In Part 15: Network Flow & Cuts, we meet the max-flow min-cut theorem and the algorithms that compute it — the backbone of bipartite matching, project selection, and more.