Paperlane

no. 6 · Monday 2 November 2026

Traveling Salesman Problem on Graphs with Proportional Independent Set

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

math.CO · via cs.DS · 13 pp

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.

comments
13 pages, 2 figures
fields
Combinatorics
pdf ↗ page arXiv:2610.41178 ↗