2014/07/10 by Satoru Iwata, Iwata, Satoru, Alantha Newman +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.2844
Proceedings of WG 2014
arxiv created 2014/07/10 · arxiv updated 2014/07/11
We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of vertices. For a graph G, if we can find a spanning tree T and a simple cycle that contains the vertices with odd-degree in T, then we show how to combine the classic "double spanning tree" algorithm with Christofides' algorithm to obtain a TSP tour of length at most (4n)/(3). We use this approach to show that a graph containing a Hamiltonian path has a TSP tour of length at most 4n/3. Since a Hamiltonian path is a spanning tree with two leaves, this motivates the question of whether or not a graph containing a spanning tree with few leaves has a short TSP tour. The recent techniques of Mömke and Svensson imply that a graph containing a depth-first-search tree with k leaves has a TSP tour of length 4n/3 + O(k). Using our approach, we can show that a 2(k-1)-vertex connected graph that contains a spanning tree with at most k leaves has a TSP tour of length 4n/3. We also explore other conditions under which our approach results in a short tour.