Approximating graphic TSP by b-matchings

Authors: Swati Gupta, Mehrdad Sohrabi, Levent Tunçel

Submitted to arXiv on 10 Nov. 2026
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

How to read this map? Illustrated guide

Closest papers Prior work it builds on Papers that cite it

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

  1. Very close Another approach to the problem
    Approximating Graphic TSP by Matchings
    Tobias 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…

  2. Very close Another approach to the problem
    4/3-Approximation of Graphic TSP
    A. Ç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.

  3. Very close Same question
    A -approximation algorithm for Graphic TSP in cubic bipartite graphs
    Jeremy 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.

  4. Very close Same question
    Graphic TSP in Cubic Graphs
    Z. 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.

  5. Very close* Same question
    Approximating Regular Graphic TSP in near linear time
    Ashish 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.

  6. Very close Same question
    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
    Andrá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…

  7. Close Broader context
    An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
    Zhihan 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}.

  8. Close* Same question
    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
    Andrá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.

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.

The illustrated guide to the papers around a paper