Traveling Salesman Problem

Problem

Given any complete (or near-complete) weighted graph, find a minimum-weight Hamilton cycle.

Discussion

Every complete graph of order $3$ or greater is Hamiltonian.

In this context, near-complete is taken to mean a graph in which the condition for Ore's Theorem is fulfilled, and to spare.

So the problem is not to just find a Hamilton cycle (for large graphs there will be plenty) but to find the best Hamilton cycle.

It is clear that, for a finite graph, there will be a finite number of Hamilton cycles to check.

However, as the number of vertices increases, then the number of Hamilton cycles increases exponentially (in fact, factorially). (See Number of Hamilton Cycles in Complete Graph). Therefore, checking every path and comparing their weights by exhaustion is, indeed, exhausting.

There is no known efficient algorithm that can be guaranteed to produce the minimum-weight Hamilton cycle required.

There are known to be some relatively efficient approximate solutions, some of which work pretty well.

The Traveling Salesman Problem has been shown to be NP-complete. This makes finding an efficient algorithm for the solution unlikely.

Note

The problem gets its name from the practical application of a salesman, traveling to a number of cities, looking for the optimum route that will keep the distance travelled to a minimum. It is understood that the distance between each pair of cities is known (thereby establishing that the game plan is a complete weighted graph).

Linguistic Note

The UK English spelling of this is Travelling Salesman Problem

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 3.2$