pith. sign in

arxiv: 2606.31907 · v1 · pith:TDLRS34Unew · submitted 2026-06-30 · 💻 cs.DS

Improved Algorithms for Bounded-Degree (Subset) Traveling Salesman Problems

Jongseo Lee , Jaehyeok Kwak , Hyung-Chan An This is my paper

Pith reviewed 2026-07-01 02:18 UTC · model grok-4.3

classification 💻 cs.DS
keywords bounded-degree TSPbicriteria approximationadditive degree violationChristofides-Serdyukov algorithmminimum spanning treetraveling salesman pathsubset TSPdegree-constrained problems
0
0 comments X

The pith

A new bicriteria algorithm for bounded-degree TSP achieves additive degree violation while matching the Christofides-Serdyukov cost ratio.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops improved bicriteria approximation algorithms for the bounded-degree traveling salesman path problem and its circuit version, plus their subset variants. It affirmatively answers an open question by showing that additive degree violations are possible instead of only multiplicative ones. The cost approximation ratio is also improved to match the analysis of the Christofides-Serdyukov algorithm for standard TSP. The improvement comes from a new lemma that lets the algorithm start from a bounded-degree minimum spanning tree whose cost and degrees are compared directly to an integral optimum rather than a fractional one.

Core claim

We present a bicriteria approximation algorithm for the bounded-degree traveling salesman path problem that achieves additive degree violation and matches the cost approximation ratio from Hoogeveen's analysis of the Christofides-Serdyukov algorithm. For the circuit version the additive violation is reduced to +2, which is best possible. For the subset path problem this is the first such algorithm with additive violation; for the subset circuit problem the cost ratio is improved.

What carries the argument

A new lemma that lets a bounded-degree minimum spanning tree serve as the starting point by comparing its cost and degrees to those of an integral optimum for the bounded-degree TSP rather than a fractional optimum.

If this is right

  • Additive degree violation becomes achievable for the path version of bounded-degree TSP.
  • The circuit version achieves the smallest possible additive violation of +2 while keeping the prior cost ratio.
  • The subset path version now has its first bicriteria algorithm with additive violation.
  • The subset circuit version has an improved cost approximation ratio.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same lemma might simplify algorithms for other degree-constrained graph problems that currently rely on Steiner trees.
  • Implementation of the new algorithm could be tested on real-world networks with degree limits to measure practical degree excess.
  • If the integral-optimum comparison technique generalizes, it may apply to other bicriteria problems that mix connectivity and degree bounds.

Load-bearing premise

The new lemma holds when the bounded-degree minimum spanning tree is compared to an integral optimum rather than a fractional optimum.

What would settle it

An instance of bounded-degree TSP where every bounded-degree minimum spanning tree violates the cost or degree inequalities required by the new lemma relative to the integral optimum.

Figures

Figures reproduced from arXiv: 2606.31907 by Hyung-Chan An, Jaehyeok Kwak, Jongseo Lee.

Figure 1
Figure 1. Figure 1: The cycle instance for n = 4. The all-ones vector on the cycle has LP cost 2n, but no exact bounded-degree integral s-t path exists. Even if arbitrary degree violations are allowed, the minimum integral solution cost is 3n − 2. B Deferred from Section 4: Bounded-Degree Subset Traveling Salesman Problems B.1 A (14/9, +6)-Approximation Algorithm for BDSTSP In this appendix, we present a (14/9, +6)-approximat… view at source ↗
read the original abstract

We present improved algorithms for several bounded-degree traveling salesman problems. In the bounded-degree traveling salesman path problem (BDTSPP), given a weighted graph G=(V,E), two endpoints s and t, and degree bounds b_v for all v, the goal is to find a minimum-cost subgraph of G that admits an Eulerian s-t path and in which each vertex v has degree at most b_v. Since deciding feasibility is already NP-hard for this problem, previous work gave a bicriteria approximation algorithm. However, that algorithm provides only a multiplicative guarantee on the degree violation, and it was left open whether additive violation is possible. We answer this open question affirmatively by giving a new bicriteria approximation algorithm with additive degree violation. The cost approximation ratio is improved as well, now matching that of Hoogeveen's analysis of the Christofides-Serdyukov algorithm. This improvement relies on a new lemma that enables the use of a bounded-degree minimum spanning tree, rather than a bounded-degree Steiner tree, as a starting point for the algorithm. The lemma compares the cost and degrees of the tree against those of an integral optimum for the bounded-degree TSP at hand, rather than those of a fractional optimum. Our lemma brings improvement to the circuit version (BDTSP) as well: we give a bicriteria algorithm that matches the previous cost approximation ratio while reducing the additive degree violation to +2, which is best possible. Subset TSP is a generalization of the standard "all-vertices" TSP, in which only a specified subset of vertices is required to be visited. We present improvements for both the circuit and the path versions. For the subset path problem (BDSTSPP), we present the first bicriteria approximation algorithm with additive degree violation; for the subset circuit problem (BDSTSP), we give an improved cost approximation ratio.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims improved bicriteria approximation algorithms for bounded-degree TSP path (BDTSPP) and circuit (BDTSP) problems as well as their subset variants (BDSTSPP, BDSTSP). It introduces a new lemma allowing a bounded-degree MST (rather than Steiner tree) to be compared directly against an integral optimum, yielding additive degree violations (+1 for paths, +2 for circuits) while matching the cost ratio from Hoogeveen's analysis of Christofides-Serdyukov; this resolves an open question on additive violations.

Significance. If the new lemma is correct, the results are significant: they provide the first additive-violation bicriteria algorithms for the path and subset-path variants, tighten the circuit violation to the best-possible +2, and improve cost ratios without introducing free parameters or circular reductions. This advances the literature on constrained TSP approximations.

major comments (2)
  1. [Abstract and §1] Abstract and §1 (new lemma): The entire set of claimed improvements (additive violations and matching Hoogeveen ratios) rests on the new lemma that bounds a degree-constrained MST against an integral optimum of the BDTSP/BDTSPP instance. The provided text states the lemma exists and works but supplies no proof; without it, the reduction from Steiner tree to MST and the preservation of additive bounds through Eulerian augmentation cannot be verified, especially for non-metric weights or when feasibility is NP-hard.
  2. [Abstract] Abstract (BDTSP circuit claim): The assertion that the algorithm reduces additive violation to +2 (best possible) while matching the prior cost ratio depends on the same lemma plus the augmentation step; any integrality gap between the MST and the integral optimum that is not controlled by the lemma would invalidate the +2 guarantee.
minor comments (2)
  1. [Abstract] The abstract states that the lemma 'brings improvement to the circuit version as well' but does not indicate where the formal statement and proof appear; adding an explicit pointer (e.g., 'Lemma 3.2') would aid readability.
  2. [Introduction] Subset variants are mentioned only briefly; a short paragraph in the introduction clarifying how the lemma extends from the all-vertices to the subset setting would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for acknowledging the potential significance of the results conditional on the lemma. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1 (new lemma): The entire set of claimed improvements (additive violations and matching Hoogeveen ratios) rests on the new lemma that bounds a degree-constrained MST against an integral optimum of the BDTSP/BDTSPP instance. The provided text states the lemma exists and works but supplies no proof; without it, the reduction from Steiner tree to MST and the preservation of additive bounds through Eulerian augmentation cannot be verified, especially for non-metric weights or when feasibility is NP-hard.

    Authors: The proof of the lemma appears in Section 3 of the full manuscript. It shows that, given any integral optimum for the bounded-degree TSP instance, there exists a spanning tree of cost at most that of the optimum whose degrees are at most those of the optimum (no additive violation in the tree itself). The proof proceeds by taking the optimum multigraph, removing cycles while preserving connectivity and degree bounds, and is valid for arbitrary nonnegative weights. We will revise the abstract and introduction to include an explicit pointer to Section 3 together with a short proof sketch so that the reduction and augmentation steps can be verified without reading the full section. revision: yes

  2. Referee: [Abstract] Abstract (BDTSP circuit claim): The assertion that the algorithm reduces additive violation to +2 (best possible) while matching the prior cost ratio depends on the same lemma plus the augmentation step; any integrality gap between the MST and the integral optimum that is not controlled by the lemma would invalidate the +2 guarantee.

    Authors: Because the lemma compares the MST directly to an integral optimum rather than a fractional relaxation, the degree of the MST is at most the optimum degree. The subsequent step that augments the tree to an Eulerian circuit adds a minimum-cost matching on the odd-degree vertices; in the worst case this matching increases the degree of any vertex by at most 2. Hence the final additive violation is +2, which is tight. The argument does not rely on metricity or on the feasibility problem being polynomial-time solvable. revision: no

Circularity Check

0 steps flagged

No significant circularity; new lemma is independent contribution

full rationale

The paper's central improvement rests on a new lemma (comparing bounded-degree MST cost/degrees to an integral optimum) that is introduced and presumably proven from first principles within the manuscript using standard techniques. No load-bearing self-citations, no fitted parameters renamed as predictions, no self-definitional reductions, and no ansatz smuggled via prior work. The derivation chain is self-contained against external algorithmic benchmarks and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard graph-theoretic axioms (undirected weighted graphs, existence of Eulerian paths under degree parity conditions) and the correctness of the new comparison lemma; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard properties of minimum spanning trees and matching in undirected graphs hold.
    Invoked implicitly when replacing Steiner tree with MST and using matching for Eulerian augmentation.

pith-pipeline@v0.9.1-grok · 5881 in / 1321 out tokens · 31473 ms · 2026-07-01T02:18:59.956821+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 28 canonical work pages

  1. [1]

    Hyung-Chan An, Robert Kleinberg, and David B. Shmoys. Improving Christofides’ algorithm for the s-t path TSP.J. ACM, 62(5), November 2015.doi:10.1145/2818310

    work page doi:10.1145/2818310 2015

  2. [2]

    Construction of bounded-degree minimum-radius spanning trees for WSNs

    Min Kyung An and Hyuk Cho. Construction of bounded-degree minimum-radius spanning trees for WSNs. In2025 IEEE 15th Annual Computing and Communication Workshop and Conference (CCWC), pages 00095–00102, 2025.doi:10.1109/CCWC62904.2025.10903839

    work page doi:10.1109/ccwc62904.2025.10903839 2025

  3. [3]

    Additive guarantees for degree- bounded directed network design.SIAM Journal on Computing, 39(4):1413–1431, 2009.doi: 10.1137/080734340

    Nikhil Bansal, Rohit Khandekar, and Viswanath Nagarajan. Additive guarantees for degree- bounded directed network design.SIAM Journal on Computing, 39(4):1413–1431, 2009.doi: 10.1137/080734340

    work page doi:10.1137/080734340 2009

  4. [4]

    Riesenfeld, and Kunal Talwar

    Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, and Kunal Talwar. What would Edmonds do? augmenting paths and witnesses for degree-bounded MSTs.Algorithmica, 55(1):157–189, 2009.doi:10.1007/S00453-007-9115-5

    work page doi:10.1007/s00453-007-9115-5 2009

  5. [5]

    Worst-case analysis of a new heuristic for the travelling salesman prob- lem

    Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman prob- lem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976

    1976

  6. [6]

    Bi-criteria approximation algorithms for bounded- degree subset TSP

    Zachary Friggstad and Ramin Mousavi. Bi-criteria approximation algorithms for bounded- degree subset TSP. In Sang Won Bae and Heejin Park, editors,33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 ofLeibniz International Proceed- ings in Informatics (LIPIcs), pages 8:1–8:17, Dagstuhl, Germany, 2022. Schloss Dagstuhl – 13 ...

    work page doi:10.4230/lipics.isaac.2022.8 2022

  7. [7]

    Takuro Fukunaga and R. Ravi. Iterative rounding approximation algorithms for degree- bounded node-connectivity network design. In53rd Annual IEEE Symposium on Found- ations of Computer Science, FOCS 2012, pages 263–272. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.30

    work page doi:10.1109/focs.2012.30 2012

  8. [8]

    Amitabha Ghosh, Ozlem Durmaz Incel, V. S. Anil Kumar, and Bhaskar Krishnamachari. Bounded-degree minimum-radius spanning trees for fast data collection in sensor networks. In2010 INFOCOM IEEE Conference on Computer Communications Workshops, pages 1–2, 2010.doi:10.1109/INFCOMW.2010.5466684

    work page doi:10.1109/infcomw.2010.5466684 2010

  9. [9]

    Michel X. Goemans. Minimum bounded degree spanning trees. In47th Annual IEEE Sym- posium on Foundations of Computer Science, FOCS 2006, pages 273–282. IEEE Computer Society, 2006.doi:10.1109/FOCS.2006.48

    work page doi:10.1109/focs.2006.48 2006

  10. [10]

    Better s-t-tours by Gao trees.Mathematical Program- ming, 172(1–2):191–207, 2018.doi:10.1007/s10107-017-1202-z

    Corinna Gottschalk and Jens Vygen. Better s-t-tours by Gao trees.Mathematical Program- ming, 172(1–2):191–207, 2018.doi:10.1007/s10107-017-1202-z

    work page doi:10.1007/s10107-017-1202-z 2018

  11. [11]

    PhD thesis, University of Alberta, November 2023

    Seyyed Ramin Mousavi Haji.Approximation Algorithms for Directed Steiner Tree and Traveling Salesman Problems. PhD thesis, University of Alberta, November 2023. URL: https://ualberta.scholaris.ca/items/977cfb75-e473-4383-938e-feb530fbede2

    2023

  12. [12]

    Hoogeveen

    J.A. Hoogeveen. Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10(5):291–295, 1991. URL:https://www.sciencedirect.com/ science/article/pii/016763779190016I,doi:10.1016/0167-6377(91)90016-I

    work page doi:10.1016/0167-6377(91)90016-i 1991

  13. [13]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A deterministic better-than-3/2 approximation algorithm for metric TSP. InInteger Programming and Combinatorial Optim- ization: 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings, pages 261–274. Springer, 2023

    2023

  14. [14]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP.Operations Research, 72(6):2543–2594, 2024. URL:https:// informs.org,doi:10.1287/opre.2022.2338

    work page doi:10.1287/opre.2022.2338 2024

  15. [15]

    On some network design problems with degree constraints.Journal of Computer and System Sciences, 79(5):725–736, 2013.doi: 10.1016/j.jcss.2013.01.019

    Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. On some network design problems with degree constraints.Journal of Computer and System Sciences, 79(5):725–736, 2013.doi: 10.1016/j.jcss.2013.01.019

    work page doi:10.1016/j.jcss.2013.01.019 2013

  16. [16]

    Jochen K¨ onemann and R. Ravi. A matter of degree: Improved approximation al- gorithms for degree-bounded minimum spanning trees.SIAM Journal on Computing, 31(6):1783–1793, 2002.arXiv:https://doi.org/10.1137/S009753970036917X,doi:10. 1137/S009753970036917X

    work page doi:10.1137/s009753970036917x 2002

  17. [17]

    Jochen K¨ onemann and R. Ravi. Quasi-polynomial time approximation algorithm for low- degree minimum-cost Steiner trees. InFST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, volume 2914 ofLecture Notes in Computer Science, pages 289–301. Springer, 2003.doi:10.1007/978-3-540-24597-1_25. 14

    work page doi:10.1007/978-3-540-24597-1_25 2003

  18. [18]

    Jochen K¨ onemann and R. Ravi. Primal-dual meets local search: Approximating MSTs with nonuniform degree bounds.SIAM Journal on Computing, 34(3):763–773, 2005.arXiv:https: //doi.org/10.1137/S0097539702418048,doi:10.1137/S0097539702418048

    work page doi:10.1137/s0097539702418048 2005

  19. [19]

    Salavatipour, and Mohit Singh

    Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, and Mohit Singh. Survivable network design with degree or order constraints.SIAM Journal on Computing, 39(3):1062–1087, 2009. doi:10.1137/070700620

    work page doi:10.1137/070700620 2009

  20. [20]

    Additive approximation for bounded degree survivable network design.SIAM Journal on Computing, 42(6):2217–2242, 2013.arXiv:https://doi.org/10

    Lap Chi Lau and Mohit Singh. Additive approximation for bounded degree survivable network design.SIAM Journal on Computing, 42(6):2217–2242, 2013.arXiv:https://doi.org/10. 1137/110854461,doi:10.1137/110854461

    work page doi:10.1137/110854461 2013

  21. [21]

    A unified algorithm for degree bounded survivable network design.Mathematical Programming, 154(1–2):515–532, 2015.doi:10.1007/ s10107-015-0858-5

    Lap Chi Lau and Hong Zhou. A unified algorithm for degree bounded survivable network design.Mathematical Programming, 154(1–2):515–532, 2015.doi:10.1007/ s10107-015-0858-5

    2015

  22. [22]

    Anand Louis and Nisheeth K. Vishnoi. Improved algorithm for degree bounded survivable network design problem. InAlgorithm Theory – SWAT 2010, volume 6139 ofLecture Notes in Computer Science, pages 408–419. Springer, 2010.doi:10.1007/978-3-642-13731-0_38

    work page doi:10.1007/978-3-642-13731-0_38 2010

  23. [23]

    Degree-constrained node-connectivity

    Zeev Nutov. Degree-constrained node-connectivity. InLATIN 2012: Theoretical Informatics, volume 7256 ofLecture Notes in Computer Science, pages 582–593. Springer, 2012.doi: 10.1007/978-3-642-29344-3_49

    work page doi:10.1007/978-3-642-29344-3_49 2012

  24. [24]

    R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt. Many birds with one stone: multi-objective approximation algorithms. InProceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, page 438–447, New York, NY, USA,

  25. [25]

    Association for Computing Machinery.doi:10.1145/167088.167209

    work page doi:10.1145/167088.167209

  26. [26]

    Ravi, Madhav V

    R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, and Harry B. Hunt III. Approximation algorithms for degree-constrained minimum-cost network-design problems.Al- gorithmica, 31(1):58–78, 2001.doi:10.1007/s00453-001-0038-2

    work page doi:10.1007/s00453-001-0038-2 2001

  27. [27]

    Ravi and Mohit Singh

    R. Ravi and Mohit Singh. Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs. InAutomata, Languages and Programming, volume 4051 ofICALP 2006, pages 169–180. Springer, 2006.doi:10.1007/11786986_16

    work page doi:10.1007/11786986_16 2006

  28. [28]

    Springer, 2003

    Alexander Schrijver.Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003

    2003

  29. [29]

    Eight-fifth approximation for the path TSP

    Andr´ as Seb˝ o. Eight-fifth approximation for the path TSP. InProceedings of the 16th Interna- tional Conference on Integer Programming and Combinatorial Optimization, IPCO’13, page 362–374, Berlin, Heidelberg, 2013. Springer-Verlag.doi:10.1007/978-3-642-36694-9_31

    work page doi:10.1007/978-3-642-36694-9_31 2013

  30. [30]

    The salesman’s improved paths through forests.Journal of the ACM, 66(4):28:1–28:16, 2019.doi:10.1145/3326123

    Andr´ as Seb˝ o and Anke van Zuylen. The salesman’s improved paths through forests.Journal of the ACM, 66(4):28:1–28:16, 2019.doi:10.1145/3326123

    work page doi:10.1145/3326123 2019

  31. [31]

    Serdyukov

    Anatoliy I. Serdyukov. O nekotorykh ekstremal’nykh obkhodakh v grafakh.Upravlyayemyye sistemy, 17:76–79, 1978

    1978

  32. [32]

    Approximating minimum bounded degree spanning trees to within one of optimal.Journal of the ACM, 62(1):1:1–1:19, 2015.doi:10.1145/2629366

    Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal.Journal of the ACM, 62(1):1:1–1:19, 2015.doi:10.1145/2629366. 15

    work page doi:10.1145/2629366 2015

  33. [33]

    Approaching 3/2 for the s-t-path TSP.Journal of the ACM, 66(2):14:1–14:17, 2019.doi:10.1145/3309715

    Vera Traub and Jens Vygen. Approaching 3/2 for the s-t-path TSP.Journal of the ACM, 66(2):14:1–14:17, 2019.doi:10.1145/3309715

    work page doi:10.1145/3309715 2019

  34. [34]

    Reducing path TSP to TSP

    Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing path TSP to TSP. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC ’20, pages 14–27. ACM, 2020.doi:10.1145/3357713.3384256

    work page doi:10.1145/3357713.3384256 2020

  35. [35]

    Reassembling trees for the traveling salesman.SIAM Journal on Discrete Math- ematics, 30(2):875–894, 2016.doi:10.1137/15M1010531

    Jens Vygen. Reassembling trees for the traveling salesman.SIAM Journal on Discrete Math- ematics, 30(2):875–894, 2016.doi:10.1137/15M1010531

    work page doi:10.1137/15m1010531 2016

  36. [36]

    residual

    Rico Zenklusen. A 1.5-approximation for path TSP. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, page 1539–1549, USA, 2019. So- ciety for Industrial and Applied Mathematics. A Deferred from Section 3: Bounded-Degree Traveling Salesman Problems A.1 Analysis of Our(5/3,+4)-Approximation Algorithm for BDTSPP Theore...

    2019