Report No. 97.266 Traveling Salesmen in the Age of Competition.pdf

Angewandte Mathematik und InformatikUniversitat zu KolnReport No. 97.266Traveling Salesmen in the Age of CompetitionbySandor P.FeketeMatthias Schmitt1997 Sandor P.FeketeMatthias SchmittCenter for Parallel ComputingUniversitat zu KolnD{50923 KolnGERMANY 1991 Mathematics Subject Classication: 90D43, 90D46Keywords: Traveling Salesman Problem (TSP), combinatorical games Traveling Salesmen in the Age of Competition(Extended Abstract)Sandor P. Fekete Matthias SchmittCenter for Parallel ComputingUniversitat zu KolnD { 50931 Koln, GermanyE-Mail: sandor@zpr.uni-koeln.demschmitt@zpr.uni-koeln.deAbstractWe propose the \Competing Salesmen Problem (CSP), a 2-player competitive version of the classicalTraveling Salesman Problem. This problem arises when we are considering two competing salesmeninstead of just one. The concern for a shortest tour is replaced by the necessity to reach any of thecustomers before the opponent does.In particular, we consider the situation where players are taking turns, moving one edge at a timewithin a graph G = (V; E). The set of customers is given by a subset VC  V of the vertices. At anygiven time, both players know of their opponents position. A player wins if he is able to reach a majorityof the vertices in VC before the opponent does.We prove that certain decision problems of this type are NP-complete; we conjecture that the generalproblem is PSPACE-complete. Furthermore, we show that the starting player may not be able to avoidlosing the game, even if both players start from the same vertex. For special cases, we can give a numberof positive results: If G is a tree T and both players start from the same vertex, we can show that thestarting player can avoid a loss. On the other hand, we can show that the second player can avoid to loseby more than one customer, provided that VC consists of leaves of T . It is unclear whether a polynomialstrategy exists for any of the two players to force this outcome, and we point out some of the d