Approximating graphic TSP by b-matchings
Authors: Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
Abstract
We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most $\frac{89}{64}=\frac{7}{5}-\frac{3}{320}$ times the value of the subtour relaxation. This improves the long-standing ratio $\frac75$ of Sebő and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most $\frac{89}{64}\approx 1.3906$. We optimize a non-linear objective function over an odd-join polytope, which uses (i) a new removable system of edges, and (ii) reconnection of subtours if the graph is disconnected. This approach gives a $\frac{13}{10}$-approximation algorithm for $4$-regular $4$-vertex-connected graphs, improving the $\frac43$ of Newman, and a $\frac43$-approximation for $k$-vertex-connected graphs of maximum degree at most $k+1$, for every $k\ge 3$. For the general graphic TSP, we construct a feasible point in the odd-join polytope, using an optimal vertex from the Subtour linear programming relaxation of TSP, which helps us bound the approximation factor by 89/64.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Approximating Graphic TSP by MatchingsTobias Moemke, O. Svensson · 2011 · IEEE Annual Symposium on Foundations of Computer Science · cited 117 times · Not summarized yet
Approximating Graphic TSP by Matchings uses matching-based edge additions and removals for graph-TSP, while this paper coordinates parity correction with reconnection through odd-join polytopes.
Abstract
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.58…
-
4/3-Approximation of Graphic TSPA. Çivril · 2023 · arXiv.org · preprint, not peer reviewed · Not summarized yet
4/3-Approximation of Graphic TSP builds a 2-edge-connected subgraph and adds a minimum-cost perfect matching, rather than optimizing removable edges and reconnection together.
Abstract
We describe a $\frac{4}{3}$-approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweighted graph. The algorithm is based on finding a minimum cost perfect matching on the odd degree vertices of a carefully computed 2-edge-connected spanning subgraph.
-
A -approximation algorithm for Graphic TSP in cubic bipartite graphsJeremy Karp, R. Ravi · 2013 · Discrete Applied Mathematics · cited 17 times · Not summarized yet
The cubic-bipartite study seeks improved Graphic TSP approximation guarantees on restricted graph classes, using cycle covers in regular bipartite graphs.
Abstract
We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time \frac{9}{7}-approximation algorithm for cubic bipartite graphs and a (\frac{9}{7}+\frac{1}{21(k-2)})-approximation algorithm for k-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.
-
Graphic TSP in Cubic GraphsZ. Dvořák, D. Král', B. Mohar · 2016 · Symposium on Theoretical Aspects of Computer Science · cited 9 times · Not summarized yet
Graphic TSP in Cubic Graphs improves Graphic TSP guarantees for cubic graphs by finding short spanning closed walks.
Abstract
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.
-
Approximating Regular Graphic TSP in near linear timeAshish Chiplunkar, S. Vishwanathan · 2014 · arXiv.org · preprint, not peer reviewed · Not summarized yet
Approximating Regular Graphic TSP in near linear time concerns approximation of Graphic TSP on regular graphs; its abstract is unavailable.
-
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 subgraphsAndrás Sebö, J. Vygen · 2012 · arXiv.org · cited 159 times · Not summarized yet
Shorter tours by nicer ears improves the general graph-TSP approximation ratio to 7/5 using optimized ear-decompositions, while this paper improves it to 89/64 using odd-join polytopes.
Abstract
We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees.For the graph-TSP itself, we improve the approximation ratio to 7/5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3.The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP r…
-
An LP-based 3/2-approximation algorithm for the graphic s-t path TSPZhihan Gao · 2013 · arXiv.org · preprint, not peer reviewed · cited 3 times · Not summarized yet
The s-t path TSP study addresses a path variant of graphic TSP and uses an LP-based algorithm with narrow cuts.
Abstract
We design a new LP-based algorithm for the graphic $s$-$t$ path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the idea of narrow cuts due to An, Kleinberg, and Shmoys. It partly answers an open question of Seb\H{o}.
-
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 subgraphsAndrás Sebö, J. Vygen · 2014 · Combinatorica · cited 86 times · Not summarized yet
Shorter tours by nicer ears targets graph-TSP approximation with a 7/5 guarantee, whereas this paper gives an 89/64 guarantee using a different framework.
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 16 November 2026.