{"id":"arxiv/2610.41178","url":"https://arxiv.org/abs/2610.41178","tags":["cs.DS","math.CO"],"score":0,"title":"Traveling Salesman Problem on Graphs with Proportional Independent Set","domain":"cs.DS","source":"arxiv","authors":["Ethan X. Fang","Shengtao Guo","Junwei Lu","Yuan Yao"],"reviews":0,"subject":"cs.DS","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}