Graph-TSP from Steiner cycles

DOI10.1007/978-3-319-12340-0_26MaRDI QIDQ2945200zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Alantha Newman, R. Ravi

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.2844

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: 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 $frac4n3$. 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"omke 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.

Recommendations

• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• Graphic TSP in cubic graphs
• Simple cubic graphs with no short traveling salesman tour
• Cubic TSP: A 1.3-Approximation
• \(\frac {13}{9}\)-approximation for graphic TSP

This page was built for publication: Graph-TSP from Steiner cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945200)