AI summary · arXiv: 2611.13585v1 · cs.DS
Approximating graphic TSP by b-matchings
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.
Ask questions about this paper to our AI assistant
How to chat with this paper? Illustrated guide
You can also chat with multiple papers at once here.
Keep this conversation — a free account saves your questions and answers, your collections of papers and your alerts.
Continue with Google Create a free accountTools for this paper
Advanced tools Premium
For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium
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.
Papers around this one
See them on a mapRanked 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.
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.