CS Paper Radar

Traveling Salesman Problem on Graphs with Proportional Independent Set

Ethan X. Fang, Shengtao Guo, Junwei Lu, Yuan Yao

cs.DS math.CO ·submitted 2026-10-30 02:58 UTC · v1

Abstract

We give a deterministic algorithm for minimum-cost Hamiltonian cycle in undirected graphs with arbitrary real edge costs and an independent set of size at least $αn$, for any fixed $3/7<α\le1/2$. It runs in $O^*(γ(α)^n)$ time for an explicit constant $γ(α)<2$; for bipartite graphs, the bound is $O^*((1+2\sqrt2)^{n/2})\approx O^*(1.957^n)$. The algorithm is based on a restricted Held--Karp dynamic program. Its state enumeration uses structural properties of minimum-cost assignments arising from a regular triangulation of a product of simplices.

Comment
13 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant

cs.DS ·2026-11-05 ·Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong +1 more
similarity 0.73
Abstract

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices, where edge costs satisfy the triangle inequality. The biased TSP (BTSP) is a natural generalization of the metric TSP, in which the vertex set is partitioned into $k$ subsets: edge costs satisfy the triangle inequality within each subset, while edges crossing the subsets may violate the triangle inequality by a certain bias factor. This model captures scenarios in which distances are metric only locally but may be distorted across different regions or types of vertices. In this paper, we study approximation algorithms for the BTSP and its path variant, the biased traveling salesman path problem (BTSPP), which asks for a minimum-cost Hamiltonian path. Previously, constant-factor approximation algorithms were known only for the case $k=2$. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer $k>2$ has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit $O(k)$-approximation algorithms with running time $N^{O(2^k k!)}$. Moreover, for the BTSPP with $k=2$, we propose an improved $(α+2+\varepsilon)$-approximation algorithm, where $α<3/2-10^{-34}$ is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of $4$

0.15

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.71
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

Improved Approximation and Hardness Bounds for $β$-TSP

cs.DS cs.CCmath.OC ·2026-11-06 ·Paul Liu, Jack Spalding-Jamieson, Da Wei Zheng
similarity 0.70
Abstract · 12 pages

The traveling salesman problem (TSP) asks for a minimum-length Hamiltonian cycle in a complete weighted graph. Its approximability depends on the edge lengths: unrestricted instances admit no constant-factor approximation unless $\mathrm{P}=\mathrm{NP}$, metric instances admit Christofides' $3/2$-approximation, and fixed-dimensional Euclidean instances admit a PTAS. We study $β$-TSP, where the edge lengths satisfy $ \ell_{uw}\leqβ(\ell_{uv}+\ell_{vw}) \qquad \forall\,u,v,w\in V\ \text{pairwise distinct}, \quad β\in\left[\tfrac{1}{2},1\right]. $ The condition arises naturally in various settings, for example, when metric travel times are combined with positive service times at the vertices. The previous best approximation algorithm, due to Böckenhauer et al., ranges from $1$ at $β=1/2$ to $3/2$ as $β$ approaches $1$. We obtain a strictly better guarantee for every $1/2<β<1$ by combining two simple constructions whose guarantees counterbalance each other. We also improve the best known approximation hardness bound for every $1/2<β<1$.

0.23

A PTAS for Euclidean Capacitated Vehicle Routing

cs.DS ·2026-11-13 ·Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
top venuehot direction similarity 0.67
Abstract

In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an $n$-node graph $G=(V,E)$ with metric edges costs $c(e)$, a depot $r\in V$, and an integer vehicle capacity $Q$. The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other $Q$ nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on $\mathbb{R}^2$, and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with $Q=n-1$), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time $(2+ε)$-approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time $n^{\log^{O(1/ε)}n}$), Jayaprakash and Salavatipour [SODA'22] (time $n^{O_ε(\log^6 n)}$), and recently Sitters [ArXiV'25] (time $n^{O_ε(\log\log n)}$). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.

0.46

Breaking the $2^n$ barrier for directed hamiltonicity

cs.DS ·2026-09-30 ·Tomohiro Koana, Soh Kumabe
theory similarity 0.67
Abstract

We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in $O^*(1.9133^n)$ time. For general directed graphs, this is the first improvement in the exponential base over the classical $O(2^n n^2)$-time algorithms of Bellman and Held--Karp (1962). To obtain this improvement, we reduce Hamiltonicity to weighted parity counting using the isolation lemma of Mulmuley, Vazirani, and Vazirani (STOC 1987). If a Hamiltonian path from $s$ to $t$ exists, assigning random polynomially bounded integer weights to the arcs gives a unique minimum-weight Hamiltonian path from $s$ to $t$ with constant probability. In particular, the path count at its total weight is odd. To compute these parities, we give a $(2-2^{-d})^n n^{O(1)}$-time algorithm for instances in which the arcs entering each vertex have at most $d$ distinct polynomially bounded integer weights. The algorithm applies the random linearization idea of Arvind and Guruswami (IPEC 2021) to the Laplacian determinant construction of Björklund, Kaski, and Koutis (ICALP 2017). To keep $d$ small, we randomly delete and duplicate arcs and partition the incoming copies at each vertex into $d$ groups, assigning a common weight to all arcs in each group. We prove that, if the input graph has a Hamiltonian path from $s$ to $t$, then with positive, albeit exponentially small, probability one can select one group at each vertex so that their union contains an odd number of such paths.

0.14

Tight asymptotic competitive ratio for the Canadian Traveller Problem on unit-weighted grids

cs.DS ·2026-10-09 ·Pierre Bergé, Vsevolod Chernyshev, Malory Marin, Alexey Pyrko, Lou Salaün
theory similarity 0.67
Abstract

We study the $k$-Canadian Traveller Problem (k-ctp), an online navigation problem introduced by Papadimitriou and Yannakakis in 1991. Given an undirected weighted graph $G=(V,E,ω)$ and two vertices $s,t\in V$, a traveller aims at navigating from $s$ to $t$ while minimizing the total distance travelled. However, up to $k$ edges of the graph may be blocked, and the traveller discovers that an edge is blocked only upon reaching one of its endpoints. The performance of an online algorithm for k-ctp is measured with the competitive ratio, which is the quotient between the distance actually traversed and the distance traversed by an omniscient traveller who knows all blockages in advance. A general lower bound $2k+1$ for the competitive ratio of deterministic algorithms remains valid even when the input graph is series-parallel, whereas constant competitive ratios can be achieved on restricted graph classes, such as cycles or unit-weighted outerplanar graphs. In this paper, we establish the first intermediate competitive ratio between constant and linear regimes. We prove that, on unit-weighted solid grid graphs, there exists an online algorithm with competitive ratio $O(\sqrt{k})$. This ratio is asymptotically tight and cannot be defeated, even on unit-weighted square grids. Finally, we show that both the unit-weighted and solidity assumptions are essential: going further with arbitrary edge weights (even on square grids) or non-solid unit-weighted grid structures yields a linear lower bound of $Ω(k)$.

0.25

Reducing Asymmetric Path TSP to Asymmetric TSP

cs.DS ·2026-11-16 ·Hong Li
similarity 0.66
Abstract · 20 pages, 3 figures

In the Asymmetric Traveling Salesman Problem (Asymmetric TSP), we are given distances between $n$ vertices that satisfy the triangle inequality but need not be symmetric, and we seek a shortest tour through all vertices. In its path version, Asymmetric Path TSP, two vertices $s$ and $t$ are prescribed, and we seek a shortest path from $s$ to $t$ through all vertices. Both problems are equivalent to their versions with arbitrary nonnegative edge costs on a directed graph, in which vertices may be visited more than once. We show that for all constants $α\ge1$ and $\varepsilon>0$, any $α$-approximation algorithm for Asymmetric TSP yields an $(α+\varepsilon)$-approximation algorithm for Asymmetric Path TSP. The best previous reduction of this kind, due to Feige and Singh, yields an $α(2+\varepsilon)$-approximation algorithm. Our result answers an open question of Traub and Vygen. Consequently, every constant-factor approximation guarantee for Asymmetric TSP carries over to Asymmetric Path TSP up to an arbitrarily small additive error.

0.23

Combinatorial optimization with bounded subdeterminants

cs.DS cs.DMmath.COmath.OC ·2026-11-09 ·Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon +3 more
similarity 0.66
Abstract · 25 pages

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

0.20