Traveling Salesman Problem on Graphs with Proportional Independent Set
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.41178
curl -X POST /api/v1/records/arxiv/2610.41178/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.41178/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'