AI summary · arXiv: 2611.13585v1 · cs.DS

Approximating graphic TSP by b-matchings

Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
Original paper Submitted to arXiv on 10 Nov. 2026 72 pages, 30 figures License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper presents a polynomial-time graphic TSP algorithm with an 89/64 approximation ratio, using degree-bounded odd-join polytopes and removable edge stars.

Question

Can the long-standing 7/5 approximation guarantee for graphic TSP be improved by coordinating parity correction with connectivity-preserving edge deletions? The paper also asks whether stronger guarantees are possible for highly connected, degree-restricted graph classes.

Method

The authors construct removable star systems from depth-first search trees and optimize parity correction and reconnection costs over degree-bounded odd-join polytopes, using polynomial-time b-matching optimization. For general connected simple graphs, they use an optimal extreme point of the subtour LP, whose support has at most 2n−3 edges, to construct a feasible certificate; they also analyze 4-regular 4-vertex-connected graphs and k-vertex-connected graphs of maximum degree at most k+1.

Findings

  • Result For general connected simple graphs, StarMatch returns a tour of length at most 89/64 times the subtour LP value.
  • Authors’ interpretation The resulting bound improves the previous 7/5 guarantee and bounds the subtour LP integrality gap on graphic instances by 89/64.
    See the passage in the paper
    This improves the long-standing ratio $\frac{7}{5}$ 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$.
  • Result For simple 4-regular, 4-vertex-connected graphs, the algorithm gives a tour bound of 13n/10−3/5.
    See the passage in the paper
    If $G$ is simple, $4$-regular, and $4$-vertex-connected, the StarReconnectionLP gives a tour of length at most $13n/10-3/5$.
  • Result For simple k-vertex-connected graphs with maximum degree at most k+1, for every k≥3, the method gives a tour bound of 4n/3−2/3.
    See the passage in the paper
    If $G$ is simple and $k$-vertex-connected, where $k\geq 3$ and $\Delta(G)\leq k+1$, the StarDeletionLP and the StarReconnectionLP both give a tour of length at most $4n/3-2/3$.
  • Authors’ interpretation The authors’ framework combines parity correction and connectivity restoration in an odd-join formulation, allowing subtour-LP values to guide the construction instead of relying on uniform join marginals.
    See the passage in the paper
    We provided a new approximation for graphic TSP by essentially constructing a point in a $T$-join polytope using the subtour LP solution. We establish feasibility of the constructed point by relating the Blossom inequalities to the subtour cut constraints.

Limitations

  • The general-graph guarantee is bounded relative to the subtour LP, and the paper does not establish the conjectured 4/3 bound for graphic instances.
    See the passage in the paper
    The $4/3$ conjecture for the subtour relaxation, stated by Goemans [8, Conjecture 1], remains open even for graphic instances.
  • The stronger general and graph-class ratios in the Lean-verified column are not presented with complete proofs in the paper.
    See the passage in the paper
    For these bounds we only sketch the proofs; complete proofs have been verified by Lean, see [36].

Why it matters

The authors argue that removable stars and degree-bounded join optimization improve the best established graphic TSP guarantee and provide stronger bounds for selected highly connected graph classes. Their approach makes the subtour solution’s individual edge values useful in parity correction while explicitly accounting for reconnection costs.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Graphic TSP subtour relaxation integrality gap degree-bounded T-joins removable stars

Read further

  • Comprehensive Summary
  • Layman's Summary
  • Blog article
  • Original abstract
The paper studies the graphic Traveling Salesperson Problem (graphic TSP): given a connected, unweighted graph, find a shortest closed walk that visits every vertex. Equivalently, the goal is to find a connected, spanning Eulerian multigraph with the fewest edge copies. The authors investigate how closely an algorithm can approach the value of the subtour linear programming relaxation, a standard lower bound on tour length. Before this work, the best stated general guarantee was a factor of \(7/5\), or 1.4, times the relaxation value. Their main contribution, StarMatch, is a polynomial-time algorithm that guarantees a tour of length at most \(89/64\), approximately 1.3906, times that value. This improves the previous guarantee and establishes the same upper bound on the subtour relaxation’s integrality gap for graphic instances. The paper also proves stronger guarantees for certain highly connected graph classes. StarMatch generalizes the removable-pairing approach used in earlier algorithms. The authors construct edge-disjoint removable stars: groups of edges incident to a common vertex, from which edges can be deleted without disconnecting the graph as long as at least one edge in each star remains. They derive these stars from a depth-first search tree, grouping a tree edge with relevant back edges. To select edges for parity correction and determine which removable edges to delete, the authors formulate degree-bounded T-join problems on an auxiliary graph. Their StarDeletionLP requires at least one edge from each star to remain. StarReconnectionLP is more flexible: it allows a join to select an entire star and accounts for restoring connectivity by adding two copies of an edge. The degree-bounded join polytopes are integral and can be optimized in polynomial time using b-matching methods. For the general guarantee, StarMatch starts with an optimal subtour solution and constructs feasible points in the auxiliary join polytope. The analysis combines two points: one tailored to the removable stars and another lifted from the subtour solution. A carefully chosen convex combination controls both parity-correction and reconnection costs. The proof also relies on the sparsity of an extreme subtour solution and on properties of the depth-first search tree. For graphs whose subtour value equals the number of vertices, the paper proves a more specific bound; for arbitrary subtour values, it derives a bound that implies the \(89/64\) ratio. For 4-regular, 4-vertex-connected graphs, the authors prove a stronger guarantee of \(13/10\), or 1.3, times the subtour value. Because that value equals the number of vertices for this graph class, they also give an additive bound on tour length. Their proof begins with a fractional point in the auxiliary polytope and repairs the few violated cut inequalities. Some repairs increase the objective, but shared corrections can address two deficiencies at once. A matching argument bounds the number of costly repairs. For \(k\)-vertex-connected graphs with maximum degree at most \(k+1\), for every \(k \geq 3\), the authors prove a \(4/3\) approximation and an additive tour-length bound. They also compare their LP framework with the Mömke–Svensson circulation method, showing that for a fixed depth-first search tree, their bounds are at least as strong as the optimized circulation-based bounds considered in the paper. The authors report additional, stronger bounds whose proofs were formalized in Lean: approximately 1.38575 for general graphic TSP and \(9/7\) for 4-regular, 4-vertex-connected graphs. They present these results as further evidence rather than as fully developed main results; the paper sketches the proofs and provides the complete formal proofs separately.

Was this synthesis useful?

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Figures and plots

Ask about a figure by number or use its question button to request visual analysis. Up to two figures and four image panels per question. Values read from plots are approximate; check the original data.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today
Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero Zotero guide
Citation alerts Citation alerts guide
Who works on it?

Among the 15 papers around this one, the name that comes back most: András Sebö (2 papers)

1 more person signs several of them. The full map adds their institutions and approaches, from the papers of the last years.

Continue with Google Create a free account: your first map is free
Weekly letter Presented in "Computing beyond AI this week" of 16 November 2026. Computing beyond AI this week: The costs hidden in our maps, networks and algorithms · Receive one by email for free

Papers around this one

See them on a map

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

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.