Research note
The TSP phase transition

https://doi.org/10.1016/S0004-3702(96)00030-6Get rights and content
Under an Elsevier user license
open archive

Abstract

The traveling salesman problem is one of the most famous combinatorial problems. We identify a natural parameter for the two-dimensional Euclidean traveling salesman problem. We show that for random problems there is a rapid transition between soluble and insoluble instances of the decision problem at a critical value of this parameter. Hard instances of the traveling salesman problem are associated with this transition. Similar results are seen both with randomly generated problems and benchmark problems using geographical data. Surprisingly, finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value in random problems. Such phase transition phenomena appear to be ubiquitous. Indeed, we have yet to find an NP-complete problem which lacks a similar phase transition.

Keywords

NP-complete problems
Complexity
Traveling salesman problem
Search phase transitions
Finite-size scaling
Eeasy and hard instances

Cited by (0)