Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

Traveling Salesman Problem on Graphs with Proportional Independent Set

  • Ethan X. Fang
  • Shengtao Guo
  • Junwei Lu
  • Yuan Yao
Open at sourcePDFDOICite

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<α≤1/2. It runs in O*(γ(α)n) time for an explicit constant γ(α)<2; for bipartite graphs, the bound is O*((1+2√2)n/2)≈ O*(1.957n). 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.

Related

  1. Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
    Sergio Caracciolo, Carlo Vanoni
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsMathematical physicsarXiv
  2. On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
    Aljaž Krpan, Janez Žerovnik
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  3. Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
    Sophia Heimann, Hung P. Hoang, Stefan Hougardy
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
    Kexin Zhang, Shubin Liu, Xinyuan Zhang +1
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
    Lina Schmidt, Julian Golak, Arne Schulz +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{fang2026traveling,
  title = {{Traveling Salesman Problem on Graphs with Proportional Independent Set}},
  author = {Ethan X. Fang and Shengtao Guo and Junwei Lu and Yuan Yao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41178},
  eprint = {2610.41178},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41178},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Traveling Salesman Problem on Graphs with Proportional Independent Set
AU  - Ethan X. Fang
AU  - Shengtao Guo
AU  - Junwei Lu
AU  - Yuan Yao
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41178
UR  - https://arxiv.org/abs/2610.41178
AB  - 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<α≤1/2. It runs in O^*(γ(α)^n) time for an explicit constant γ(α)<2; for bipartite graphs, the bound is O^*((1+2√2)^n/2)≈ 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.
ER  -