CS Paper Radar

Approximating graphic TSP by b-matchings

Swati Gupta, Mehrdad Sohrabi, Levent Tunçel

cs.DS cs.DMmath.COmath.OC ·submitted 2026-11-10 04:57 UTC · v1

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.

Comment
72 pages, 30 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP

cs.DS ·2026-10-12 ·Niklas Dahlmeier, Raoul Luqué, Philipp Pabst, Laura Vargas Koch
similarity 0.70
Abstract · 22 pages, 3 figures, 1 table, 1 linear program, 2 algorithms

We give improved approximation algorithms for two graphic TSP variants. First, we consider Multi-Depot TSP on graphic instances. In this variant, we are given an undirected graph with a set of depot vertices, and we are tasked with finding an Eulerian multi-edge set that connects each non-depot vertex to at least one depot. For this problem, Deppert, Kaul and Mnich (ESA 2023) presented a 3/2-approximation algorithm with running time exponential in the number of depots. We improve this result to a fully polynomial 3/2-approximation. Our algorithm is a variant of the classic Christofides-Serdyukov algorithm with an improved and simple analysis. On subcubic instances, we improve the approximation guarantee to 4/3 using the technique of removable pairings introduced by Mömke and Svensson (J. ACM 2016). We use a removable pairing to construct a set of disjoint cycles that can be completed to a cheap feasible solution. Second, we consider the Graphic Multi-Path TSP, which was previously considered by Alimi, Dahlmeier, Mömke, Pabst and Vargas Koch (SOSA 2026) who give a 2-approximation for this problem. Additionally, the authors present a reduction that shows that any better-than-two approximation for Graphic Multi-Depot TSP immediately leads to an improvement for Graphic Multi-Path TSP. We give an improved algorithm and analysis that yield an approximation guarantee of 1.9304.

0.17

Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP

cs.DS ·2026-10-13 ·Sharareh Alipour, Ali Nowzari
similarity 0.66
Abstract

We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high probability, in $n^{2-Ω_\eps(1)}$ time, where $\cstar=2(\sec1-\tan1)$. This improves the $3/2+\eps$ factor of direct matching estimation in this subquadratic regime~\cite{BhattacharyaKissSaranurak2023} and of the faster near-linear estimator~\cite{BehnezhadEtAl2024}. A single random vertex order defines an implicit bipartite graph whose matchings project to path covers. An alternating-permutation analysis shows that its expected maximum matching size is at least $\cstar$ times the optimum path-cover size. On long paths, even the best of polynomially many uniform orders retains only a $\cstar+o(1)$ fraction with high probability. In semi-streaming, we construct deterministic $(5/7-\eps)$-approximate unweighted path covers and $(9/7+\eps+5/(7n))$-approximate $(1,2)$-TSP tours, improving the respective $2/3-\eps$ and $4/3+\eps+1/n$ guarantees in~\cite{AlipourFarokhnejadMoemke2025}. For nonnegative weights, we obtain $2/3-\eps$ for path cover and Max-TSP, improving the earlier asymptotic $7/12-\eps$ Max-TSP bound. These algorithms use $\poly(1/\eps)$ passes independent of $n$ and $O(n\log(n/\eps)\poly(1/\eps))$ words. We compute two approximate matchings separated by edge deletion. A cycle-compensation lemma accounts for the weight removed when breaking their cycles. For unweighted graphs, a third approximate matching on a simple auxiliary graph with at most $2n$ vertices chooses component connections; a Tutte--Berge count proves the stronger bound.

0.25

A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP

cs.DS ·2026-09-28 ·Zhao Song
theory similarity 0.65
Abstract

Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality gap of the subtour-elimination LP [KKO22], with an explicit constant $\varepsilon>1.00000\cdot10^{-36}$. Gurvits, Klein, and Leake subsequently improved the certified saving to $2.18000\cdot10^{-34}$ [GKL24]. In this paper, we obtain a randomized polynomial-time $(3/2-\varepsilon)$-approximation for every fixed $0<\varepsilon<\varepsilon_\star$, where $\varepsilon_\star>2.78621\cdot10^{-18}$, and consequently the subtour-elimination LP has integrality gap at most $3/2-\varepsilon_\star$. The classical worst-case integrality-gap lower bound is $4/3$ [Wil90].

0.39

A Common Improved Bound for Asymmetric TSP and Path TSP

cs.DS ·2026-11-13 ·MohammadTaghi Hajiaghayi, Changki Yun
similarity 0.64
Abstract

We give polynomial-time $(R_*+\varepsilon)$-approximation algorithms for asymmetric TSP and asymmetric path TSP, for every fixed $\varepsilon>0$, where $R_*=6+\sqrt2+\sqrt{15+6\sqrt2}\approx12.2604$. Both guarantees hold relative to the corresponding subtour relaxations, whose integrality ratios are therefore at most $R_*$. This improves the previous guarantees of below $14.7$ for asymmetric TSP and $15$ for asymmetric path TSP [Vygen, 2026]. Our algorithms strengthen subtour covers and recursive augmentation in the laminar framework [Svensson, Tarnawski, Vegh, JACM'20; Traub, Vygen, 2025]. The recursive analysis retains the paths through contracted regions and accounts jointly for their cost and the dual mass they visit. We also improve the reduction from asymmetric path TSP to vertebrate pairs [Traub, Vygen, 2025] by comparing two initial walks with complementary completion bounds. Applied to Vygen's existing vertebrate-pair algorithm, this reduction alone improves the path factor from $15$ to below $14.7$, matching his asymmetric TSP guarantee.

0.54

Polynomial $(2α+\varepsilon)$- and Quadratic $4$-Approximation Algorithms for the Biased Traveling Salesman Problem in Bipartitioned Networks

cs.DS ·2026-11-04 ·Jingyang Zhao, Trung Q. Duong, Een-Kee Hong, Hyundong Shin
similarity 0.63
Abstract

The traveling salesman problem (TSP) is one of the fundamental problems in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices. For the metric TSP, where edge costs satisfy the triangle inequality, a long line of work has produced constant-factor approximation algorithms, culminating in the best-known approximation ratio $α<3/2-10^{-36}$. The biased TSP (BTSP) generalizes the metric TSP to bipartitioned networks: the vertex set is partitioned into two subsets, edge costs satisfy the triangle inequality within each subset, while edges crossing the partition may violate it by a certain bias factor. This model captures heterogeneous routing scenarios in which distances are metric only locally but may be distorted across different regions or vertex types. Previously, the only known result for the BTSP was a $7/2$-approximation algorithm with running time $O(N^3)$. In this paper, we present two new approximation algorithms that significantly improve the state of the art. The first achieves an approximation ratio of $2α+\varepsilon$ (strictly less than $3$) in polynomial time $N^{O(1)}$ for any constant $\varepsilon>0$, where the exponent grows at least linearly with $1/\varepsilon$. The second achieves a $4$-approximation in only $O(N^2)$ running time, reducing the previous cubic-time bound by a full polynomial factor. These advances directly support emerging networked systems---including multi-tier 6G architectures and hybrid quantum-classical networks---where cross-region transitions incur biased and non-metric overheads.

0.25

Minimum Sum Vertex Cover via Minimum Vertex Cover

cs.DS cs.DM ·2026-09-22 ·Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
theory similarity 0.63
Abstract

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

0.20

TSP instances that require exponentially many subtour elimination constraints

cs.DM math.CO ·2026-11-11 ·Eleonora Vercesi, Austin Buchanan
theory similarity 0.62
Abstract

We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(Ω(φ^n)\), where \(φ\approx 1.618\) is the golden ratio. A node-splitting reduction gives metric instances with \(Ω(φ^{n/2})\) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require exponentially many SECs. Concorde struggles on them, with solve times growing exponentially despite tiny integrality gaps.

0.28

A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity

cs.DS ·2026-09-13 ·Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur
similarity 0.62
Abstract

In the $(p,q)$-Flexible Graph Connectivity problem, the input consists of non-negative integers $p$ and $q$ and a graph $G=(V, E)$ whose edges are classified into safe and unsafe edges with non-negative edge costs. A subgraph H of G is $(p,q)$-Flex-Connected if every non-empty proper subset of vertices has either at least $p$ safe edges or at least $p+q$ total edges crossing it. The goal is to find a minimum cost subset $F\subseteq E$ of edges such that the subgraph $(V, F)$ is $(p,q)$-Flex-Connected. We give a $(p+q)^{O(pq)}$-approximation for this problem, which in particular implies a constant approximation for every fixed constants $p$ and $q$. We achieve this by designing a $(p+q)^{O(pq)}$-approximation for the augmentation problem of finding a minimum cost subset of edges to add to make a (p,q-1)-Flex-Connected graph into a (p,q)-Flex-Connected graph. Underlying the augmentation algorithm is a structural result showing that all deficient cuts can be represented by min rooted-cuts in a $(p+q)^{pq}$-sized collection of digraphs. This structural result was discovered by ChatGPT Astra.

0.27