1. The problem, stated precisely
Given a complete weighted graph $G = (V, E, w)$ on $n$ vertices with $w : E \to \mathbb{R}_{\geq 0}$, find a Hamiltonian cycle — a cycle that visits every vertex exactly once and returns to its start — of minimum total weight.
Three things to notice in that definition. First, the graph is complete: you can travel directly between any pair of cities. (If you can't, you simply assign the missing edges weight $\infty$ and lose nothing.) Second, the requirement is "exactly once" — no revisits and no skips. Third, the goal is the cycle itself, but the value being minimised is the sum of edge weights along it.
A useful subdivision: in the metric TSP, weights satisfy the triangle inequality, $w(u,v) \leq w(u,x) + w(x,v)$ for all $u, v, x$. Distances on a map satisfy this. Airline fares often do not. This distinction matters because the best approximation guarantees in section 6 only hold for metric instances.
2. Brute force and the $(n-1)!/2$ wall
The most direct attack is to enumerate every possible tour, compute its total weight, and keep the cheapest. How many tours are there?
A tour is a circular sequence of all $n$ vertices. Fix the starting city (without loss of generality — every tour has $n$ rotations that visit the same edges, so we divide one out). That leaves $(n-1)!$ orderings of the remaining cities. But each tour can also be traversed in two directions — clockwise and counter-clockwise — and these traverse the exact same edges with the same total weight, so we divide by 2:
$$ \text{number of distinct tours} = \frac{(n-1)!}{2}. $$That ratio looks innocuous and explodes spectacularly.
| $n$ cities | $(n-1)!/2$ tours | At 1 µs per tour |
|---|---|---|
| 5 | 12 | 12 µs |
| 10 | 181{,}440 | 0.18 s |
| 15 | 43{,}589{,}145{,}600 | 12 hours |
| 20 | $\approx 6.1 \times 10^{16}$ | $\approx 2000$ years |
| 25 | $\approx 3.1 \times 10^{23}$ | $\approx 10^{10}$ years |
By 25 cities, brute force is older than the universe. And 25 cities is nothing — modern industrial TSP instances have hundreds of thousands.
People sometimes describe TSP brute force as "exponential". It's worse: it's factorial. Stirling's approximation gives $n! \sim \sqrt{2\pi n}\,(n/e)^n$, which grows faster than $2^n$ for any $n$ past about 3. Doubling $n$ doesn't double the work — it raises the work to a power.
3. Why TSP is NP-hard
"NP-hard" means, informally: at least as hard as the hardest problems in NP. A polynomial-time algorithm for TSP would imply $\mathrm{P} = \mathrm{NP}$ — and would resolve the most famous open question in computer science in the affirmative.
The standard proof reduces from the Hamiltonian-cycle problem: given a graph $G$ (no weights), does it contain a Hamiltonian cycle? This problem is known to be NP-complete. The reduction to TSP is one line:
- Take any graph $G$ on $n$ vertices.
- Build a complete graph $G'$ on the same vertices. Assign weight $1$ to every edge that was present in $G$, and weight $2$ to every edge that wasn't.
- Solve TSP on $G'$. If the optimal tour has total weight $n$, then it used only weight-$1$ edges — meaning $G$ contains a Hamiltonian cycle. Otherwise the tour had to use at least one weight-$2$ edge, meaning $G$ has no Hamiltonian cycle.
The reduction is polynomial-time. So a polynomial-time TSP solver would give a polynomial-time Hamiltonian-cycle solver, which would prove $\mathrm{P} = \mathrm{NP}$. Hence the hardness conclusion: under the standard complexity assumptions, no polynomial-time exact algorithm for TSP exists.
"NP-hard" doesn't mean "unsolvable" — it means "not known to be solvable in polynomial time, and probably not". People solve TSP exactly all the time, with branch-and-bound and integer-programming techniques. The Concorde solver has handled instances with tens of thousands of cities optimally. But the worst-case complexity remains super-polynomial.
4. Decision vs optimisation
Complexity theory is usually framed in terms of decision problems — yes/no questions. The decision version of TSP is:
Given a weighted graph $G$ and a budget $B$, is there a tour with total weight at most $B$?
The optimisation version is the natural one: "find the cheapest tour". These two versions are polynomially equivalent — if you can solve one, you can solve the other with a polynomial amount of extra work (binary-search on $B$ for one direction; compare the answer to $B$ for the other). So when we say "TSP is NP-hard", we are really saying both versions are intractable in the same sense.
The framing matters because the formal class NP is defined for decision problems, and complexity statements like "TSP is NP-complete" technically apply to the decision version. The optimisation version is "NP-hard" — at least as hard, but not itself in NP because a solution isn't a yes/no.
5. The nearest-neighbour heuristic
If you can't afford optimal, settle for fast. The simplest TSP heuristic is greed:
- Start at any city.
- Repeatedly travel to the nearest unvisited city.
- When all cities have been visited, return to the start.
That's it. Nearest-neighbour runs in $O(n^2)$ time and is trivial to implement. It also produces tours that are, on average, about 25% longer than optimal — and in adversarial cases, arbitrarily worse. For metric TSP it's known that nearest-neighbour can produce tours up to $\Theta(\log n)$ times the optimum.
So why use it at all? Two reasons. First, on real-world instances it's often within a few percent of optimal — bad in the worst case, decent in the average case. Second, it's the standard starting point for improvement heuristics like 2-opt and Lin–Kernighan, which need an initial tour to refine.
6. Christofides: a 1.5-approximation
For metric TSP (weights obey the triangle inequality), Christofides' 1976 algorithm produces a tour whose total weight is at most $1.5$ times the optimum. That guarantee — "no worse than 1.5× best possible, ever" — held the record from 1976 until 2020, when a paper by Karlin, Klein, and Oveis Gharan inched it down to roughly $1.5 - 10^{-36}$ via a complex randomised construction. For practical purposes, Christofides is still the bound to know.
The algorithm combines two structures from elsewhere in the chapter:
- Build the minimum spanning tree $T$ of the graph (Kruskal or Prim). The MST gives a connected skeleton; its total weight is a lower bound on the optimal tour weight (any tour, minus one edge, is a spanning tree).
- Identify the odd-degree vertices of $T$. There's an even number of them (a consequence of the handshake lemma).
- Find a minimum-weight perfect matching $M$ on those odd-degree vertices, using only the original graph's edges.
- Add $M$ to $T$. The result, $T \cup M$, has every vertex of even degree — so it admits an Eulerian circuit, a closed walk using every edge exactly once.
- Walk the Eulerian circuit and shortcut repeats. When the walk is about to revisit a vertex, jump ahead to the next unvisited one. The triangle inequality guarantees the shortcut is no longer than the original two-edge segment, so the result is a Hamiltonian cycle no heavier than the Eulerian circuit.
The cost analysis is elegant. The MST weighs at most $\mathrm{OPT}$ (the optimal tour minus one edge is a spanning tree). The matching weighs at most $\mathrm{OPT}/2$ (a clever pigeonhole argument: the optimal tour, restricted to the odd-degree vertices, splits into two perfect matchings, one of which is at most half the tour). Total: $\mathrm{OPT} + \mathrm{OPT}/2 = 1.5 \cdot \mathrm{OPT}$.
Christofides stitches together three independent classical results — MSTs, Euler circuits, and minimum-weight matching — and gets a worst-case bound that nothing has meaningfully beaten in nearly fifty years. The bound is also tight: families of instances exist where Christofides really does produce tours close to $1.5 \cdot \mathrm{OPT}$.
7. Lin–Kernighan and 2-opt local search
Christofides gives a strong worst-case guarantee. In practice, what almost everyone actually runs are local-search heuristics: start with some tour (nearest-neighbour, Christofides, anything), then iteratively swap edges to improve it.
The cleanest local-search move is 2-opt:
- Pick two edges $(a, b)$ and $(c, d)$ in the current tour.
- Remove them, reverse the path between $b$ and $c$, and reconnect with $(a, c)$ and $(b, d)$.
- If the new tour is shorter, keep it. Otherwise revert.
- Repeat until no swap improves the tour — the tour is then "2-opt optimal".
The visual intuition is "uncrossing": whenever two tour edges cross each other in the plane, swapping them with their non-crossing counterparts is guaranteed to be shorter by the triangle inequality. A 2-opt-optimal Euclidean tour has no self-crossings.
The Lin–Kernighan heuristic (1973) generalises 2-opt by allowing more complex chains of edge swaps — effectively considering $k$-opt moves for variable $k$, with clever pruning so the search remains tractable. In practice, Lin–Kernighan and its descendants (notably Helsgaun's LKH) routinely produce tours within fractions of a percent of optimal on instances with thousands of cities, in seconds.
8. Why approximation is the real game
The honest summary of TSP looks like this:
- Exact solvers (Concorde, branch-and-cut) can handle surprisingly large instances — tens of thousands of cities, in some cases — but they offer no polynomial-time guarantees and can blow up on adversarial inputs.
- Approximation algorithms (Christofides) give worst-case ratios on metric instances but are not what practitioners actually run.
- Heuristic local search (Lin–Kernighan, LKH) gives no worst-case guarantee but produces near-optimal tours on real-world inputs, fast.
For pure non-metric TSP, no constant-factor approximation is possible unless $\mathrm{P} = \mathrm{NP}$. The triangle inequality is what makes Christofides' analysis go through — without it, the "shortcut" step is no longer safe. This is why "metric vs non-metric" is the first question to ask about any new TSP variant.
TSP is the prototype of a whole genre of combinatorial problems where the practical question is not "can I solve this optimally?" but "how close to optimal can I get, and how confident am I in the gap?" Whole subfields — approximation algorithms, integer programming, metaheuristics — exist primarily to answer that question.
9. Common pitfalls
The single most common student mistake is concluding nearest-neighbour gives the right answer because each individual step is locally cheapest. Local greed compounds badly: a tiny saving early can force a huge cost at the end. Always check by trying a different start city — if the answer changes, greedy was wrong.
Christofides' 1.5-factor guarantee only applies when the edge weights satisfy the triangle inequality. On non-metric instances, the shortcut step can produce arbitrarily bad tours, and in fact no constant-factor approximation is possible at all (unless $\mathrm{P} = \mathrm{NP}$). Always check the assumption before quoting the bound.
"Exponential" is too kind. The brute-force enumeration is $(n-1)!/2$, which grows faster than any exponential $c^n$. A "small" speedup that turns $n!$ into $n!/100$ buys you almost nothing — the factorial still wins by $n \approx 5$ more cities.
NP-hardness is a worst-case statement. Real-world TSP instances often have structure (planar layouts, sparse non-trivial edges, geometric locality) that exact solvers can exploit. The Concorde solver has provably-optimal solutions for instances of hundreds of thousands of cities. Don't conclude "TSP is unsolvable" — conclude "TSP has no known polynomial-time algorithm that works on all inputs".
10. Worked examples
Example 1 · Enumerate all tours of $K_4$
Setup. Cities $\{A, B, C, D\}$, weights:
| Edge | Weight |
|---|---|
| A–B | 1 |
| A–C | 4 |
| A–D | 3 |
| B–C | 2 |
| B–D | 5 |
| C–D | 6 |
Count. $(n-1)!/2 = 3!/2 = 3$ distinct tours.
Enumerate. Fix start at $A$:
- $A \to B \to C \to D \to A$: $1 + 2 + 6 + 3 = 12$.
- $A \to B \to D \to C \to A$: $1 + 5 + 6 + 4 = 16$.
- $A \to C \to B \to D \to A$: $4 + 2 + 5 + 3 = 14$.
Optimal tour: $A \to B \to C \to D \to A$ with total weight $12$.
Example 2 · Nearest-neighbour on the same graph
Start at $A$.
- At $A$: nearest unvisited is $B$ (weight 1). Move to $B$.
- At $B$: nearest unvisited is $C$ (weight 2). Move to $C$.
- At $C$: only $D$ remains (weight 6). Move to $D$.
- Return $D \to A$ (weight 3).
NN tour: $A \to B \to C \to D \to A$, total $1 + 2 + 6 + 3 = 12$. Lucky — it matches the optimum.
Start at $C$ instead.
- At $C$: nearest is $B$ (2). Move.
- At $B$: nearest unvisited is $A$ (1). Move.
- At $A$: only $D$ remains (3). Move.
- Return $D \to C$ (6).
NN tour from $C$: $C \to B \to A \to D \to C$, total $2 + 1 + 3 + 6 = 12$. Same edges as above (tours are circular). On bigger graphs, different starts typically give different — and differently bad — tours.
Example 3 · Sketch Christofides on a 4-city instance
Setup. Same 4 cities as Example 1.
Step 1 — MST. Edges sorted: $A{-}B(1), B{-}C(2), A{-}D(3), A{-}C(4), B{-}D(5), C{-}D(6)$. Kruskal picks $A{-}B, B{-}C, A{-}D$. Weight: $1 + 2 + 3 = 6$.
Step 2 — Odd-degree vertices. Degrees in the MST: $A = 2, B = 2, C = 1, D = 1$. Odd-degree set: $\{C, D\}$.
Step 3 — Minimum-weight matching on $\{C, D\}$. Only one matching exists: the single edge $C{-}D$ with weight $6$.
Step 4 — Combine. $T \cup M$ has edges $\{A{-}B, B{-}C, A{-}D, C{-}D\}$. Every vertex now has even degree.
Step 5 — Eulerian circuit, shortcutting. Walking the Eulerian circuit and shortcutting yields, for instance, $A \to B \to C \to D \to A$ with weight $12$.
Christofides upper bound: $\mathrm{MST} + \tfrac{1}{2}\mathrm{OPT} \leq 6 + 6 = 12$. Actual tour weight: $12$. ✓
On this tiny example, Christofides happens to find the exact optimum. On larger instances it stays within the 1.5 factor.
Example 4 · When greedy is much worse than optimal
Setup. Four cities on a line at positions $0, 1, 10, 11$.
Optimal tour. $0 \to 1 \to 11 \to 10 \to 0$: weight $1 + 10 + 1 + 10 = 22$.
Nearest-neighbour from $0$.:
- At $0$: nearest is $1$ (distance 1).
- At $1$: nearest unvisited is $10$ (distance 9). (Not $11$, which is 10 away.)
- At $10$: only $11$ remains (distance 1).
- Return $11 \to 0$: distance 11.
NN tour weight: $1 + 9 + 1 + 11 = 22$. Same as optimal here.
Now start at city $1$.:
- $1 \to 0$ (1), $0 \to 10$ (10), $10 \to 11$ (1), $11 \to 1$ (10). Total: $1 + 10 + 1 + 10 = 22$.
For this symmetric metric example NN is robust. Construct a slightly less regular instance (e.g. $0, 1, 100, 101$ with a long-distance return forced) and the ratio between NN and optimal can be made arbitrarily large — that's the worst-case behaviour the heuristic guarantees nothing about.
Example 5 · 2-opt swap on a crossed tour
Setup. Four cities at $(0,0), (1,0), (1,1), (0,1)$ — a unit square. Consider the tour $(0,0) \to (1,1) \to (1,0) \to (0,1) \to (0,0)$, which has the two diagonals crossing.
Compute the weight. The diagonals contribute $\sqrt{2}$ each, the off-diagonals contribute $1$ each. Total: $\sqrt{2} + 1 + \sqrt{2} + 1 \approx 4.83$.
2-opt swap. Remove the diagonals $(0,0){-}(1,1)$ and $(1,0){-}(0,1)$. Reverse the path between them. Reconnect with $(0,0){-}(1,0)$ and $(1,1){-}(0,1)$, giving the perimeter tour.
New weight: $1 + 1 + 1 + 1 = 4$. Improvement of $\sqrt{2} \cdot 2 - 2 \approx 0.83$. And the new tour has no crossings — it's 2-opt optimal.