no. 6 · Monday 2 November 2026
Traveling Salesman Problem on Graphs with Proportional Independent Set
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