Problem — Around the World
In 1856, William Hamilton presented a famous geometric challenge: given a dodecahedron with 20 vertices, each associated with a different city, one must trace a path along the edges that visits every city exactly once, returning to the starting vertex.
Why is the problem difficult in practice?
At first glance, the Hamiltonian cycle problem seems simple: find a path that visits each vertex exactly once and returns to the starting point. In practice, however, this problem quickly becomes computationally difficult.
The main difficulty lies in the fact that no efficient algorithm is known that solves the Hamiltonian cycle problem for all graphs. The number of possible orders in which the vertices can be visited grows factorially: for a graph with \(n\) vertices, there are up to \(n!\) permutations to consider in the worst case.
Even when using pruning techniques, backtracking, and heuristics, the search space grows explosively. A graph with only 20 vertices already has more than \(2.4 \times 10^{18}\) possible visiting sequences, which makes any brute-force approach infeasible.
This combinatorial explosion explains why Hamiltonian problems play a central role in computational complexity theory, serving as classical examples of NP-complete problems. Verifying whether a given path is Hamiltonian is easy; finding one, on the other hand, may require exploring an exponential number of possibilities.
In practice, this means that exact solutions are only feasible for small or highly structured graphs. For larger instances, algorithms rely on heuristics, approximations, or problem-specific knowledge, sacrificing absolute guarantees of efficiency.