SOMETIMES TRAVELING IS EASY - THE MASTER TOUR PROBLEM

In 1975, Kalmanson proved that if the distance matrix in the travellin g salesman problem (TSP) fulfills certain combinatorial conditions (th at are nowadays called the Kalmanson conditions) then the TSP is solva ble in polynomial time [Canad. J. Math., 27 (1995), pp. 1000-1010]. We deal with the problem of deciding, for a given instance of the TSP, w hether there is a renumbering of the cities such that the correspondin g renumbered distance matrix fulfills the Kalmanson conditions. Two re sults are derived: first, it is shown that-in case it exists-such a re numbering can be found in polynomial time. Secondly, it is proved that such a renumbering exists if and only if the instance possesses the s o-called master tour property. A recently posed question by Papadimitr iou is thereby answered in the negative.