Mathematics
Hamiltonian Cycles and the Traveling Salesman Problem
Quick fact
The traveling salesman problem is NP-hard, meaning that no known algorithm can solve it exactly in time that grows merely polynomially with the number of cities—even though a proposed solution can be checked instantly.
Why this is interesting
You have to visit every city on your list exactly once and return home—but which route is shortest? The answer may seem simple, yet it hides one of the deepest mysteries in computer science.
Read the full explanation
Understanding Hamiltonian Cycles and the Traveling Salesman Problem
Imagine a graph as a collection of dots (vertices) connected by lines (edges). A Hamiltonian cycle is a path that starts at one dot, visits every other dot exactly once, and then returns to the starting dot, without repeating any dot. Not every graph has such a cycle, and determining whether one exists is already a difficult problem. Now suppose each edge has a weight, such as distance or cost. The traveling salesman problem (TSP) asks not just for any Hamiltonian cycle, but for the one with the smallest total weight. This distinction—finding any cycle versus finding the best cycle—is crucial. The first is a yes/no question; the second is an optimization. Because the number of possible cycles grows factorially with the number of cities, even a small instance can have an astronomical number of routes to compare. TSP is the most famous example of a problem that is easy to state but computationally hard to solve optimally.
A deeper explanation
Why is TSP so hard? The naïve approach is brute force: list every possible Hamiltonian cycle and compute its total length. For n cities, there are (n-1)!/2 distinct cycles (accounting for rotations and reflections). For just 20 cities, that’s about 6×10^16 cycles—far more than any computer can enumerate. The reason no efficient algorithm is known stems from the structure of the problem: it is NP-hard. This means that if you could solve TSP quickly, you could also solve every other NP problem quickly, which would resolve the P vs NP question. In practice, we often rely on heuristics and approximation algorithms that find good—but not guaranteed optimal—routes quickly. The traveling salesman problem appears in logistics, circuit board drilling, DNA sequencing, and even in the order in which a telescope observes celestial objects. Its study has inspired a rich theory of computational hardness and approximation, making it a cornerstone of discrete mathematics and computer science.