Four point conditions and exponential neighborhoods for the symmetric TSP

In most of the known polynomially solvable cases of the symmetric travelling salesman problem (TSP) which result from restrictions on the underlying distance matrices, the restrictions have the form of so-called four-point conditions (the inequalities involve four cities). In this paper we treat all possible (symmetric) four-point conditions and investigate whether the corresponding TSP can be solved in polynomial time. As a by-product of our classification we obtain new families of exponential neighborhoods for the TSP which can be searched in polynomial time and for which conditions on the distance matrix can be formulated so that the search for an optimal TSP solution can be restricted to these exponential neighborhoods.