Pith. sign in

REVIEW 3 minor 19 references

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP

T0 review · 0 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Graphic Multi-Path TSP has a deterministic 2-approximation algorithm; Ordered TSP in graphic metrics reaches 1.791.

desk verdict Solid paper: a clean 2-approximation for Graphic Multi-Path TSP and a nice extension to Ordered TSP, with proofs that check out. read the letter →

arxiv 2509.00448 v1 pith:UO2N57XA submitted 2025-08-30 cs.DS

Morteza Alimi , Niklas Dahlmeier , Tobias Mömke , Philipp Pabst , Laura Vargas Koch This is my paper · ORCID
classification cs.DS MSC 68W2590C2790C35
keywords GraphicMulti-PathTSPapproximationalgorithmLPintegralitygapflowdecompositionOrderedOdd-joinrandomizedroundingvehiclerouting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that two path-constrained versions of the Traveling Salesman Problem (TSP) get much better approximation guarantees when the input is a graphic metric—that is, shortest-path distances in a connected unweighted graph. Its main result is a deterministic 2-approximation for Graphic Multi-Path TSP, improving the previous 2.214-approximation known for general metrics, and as a corollary the LP relaxation has integrality gap at most 2. The algorithm solves a flow LP, decomposes each commodity's flow into paths, samples one path per source-sink pair with probability equal to its flow value, then attaches every vertex missed by the sampled paths at cost two. The analysis reduces to a per-vertex inequality: the expected sampling cost plus twice the probability of being left out never exceeds the LP contribution of that vertex. The same sampling framework, combined with a parity-correction step using an Odd-join, gives a 1.791-approximation for Graphic Ordered TSP, improving the previous 1.868 general-metric bound.

What carries the argument

The engine is the flow LP (constraints (1)–(7)) on the bidirected unit-edge graph, whose optimal solution decomposes into per-commodity paths and cycles. Sampling paths according to their flow weights, then covering leftover vertices with doubled arcs, is carried by the identity z + 2e^{-z} ≤ 2 max{1, z}: the first term is the expected sampled cost of a vertex, the second is twice its probability of being left uncovered, and the LP gives the non-terminal coverage constraint used to compare with the optimum. For Ordered TSP the second ingredient is the Odd-join (an edge set correcting vertex-degree parity): both the reconnection edges and half the LP flow are Odd-joins, and the algorithm take

What would settle it

Run an exact solver on small connected unweighted graphs and terminal pairs, comparing the integer optimum with the LP optimum; any instance with ratio strictly greater than 2 would refute the claimed integrality gap and hence Theorem 1.1.

Watch

Extended reading notes

Core claim

Central claim: Theorem 1.1 gives a 2-approximation for Graphic Multi-Path TSP. The algorithm solves a flow LP, decomposes each commodity's flow into paths, samples one path per commodity with probability equal to its flow value, and reconnects every missed vertex at cost two using doubled arcs—possible in a strongly connected bidirected unit-edge graph. The per-vertex analysis bounds expected sampling cost z_v plus expected reconnection cost 2e^{-z_v} by 2z_v using the LP constraint z_v ≥ 1, so the expected total is at most 2 LP; derandomization makes it deterministic. The same sampling framework with a parity-correction step gives a (1+e/(2e−2))-approximation for Graphic Ordered TSP, and a

Load-bearing premise

The argument assumes that every vertex missed by the sampled paths can be attached to an already-covered vertex by adding exactly two directed edges (one in, one out); this exact cost-two attachment is true for unweighted bidirected graphs but breaks for general metric costs, which is why the result is graphic rather than metric.

Editorial extensions

If this is right

  • Graphic Multi-Path TSP has a deterministic polynomial-time 2-approximation, and the LP relaxation for the problem has integrality gap at most 2.
  • The previous best general-metric factor of 2.214 is improved to 2 for graphic metrics without using arborescence sampling or a separate parity-correction phase.
  • Graphic Ordered TSP admits a 1 + e/(2e−2) < 1.791 approximation, improving the 1.868 general-metric bound.
  • Any (2−δ)-approximation for Graphic Uncapacitated Multi-Depot VRP (the special case si = ti) automatically gives a (2−f(δ))-approximation for Graphic Multi-Path TSP.
  • The algorithm is structurally simple: one LP solve, a flow decomposition, sampling, and a greedy reconnection, all polynomial-time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The per-vertex bound z + 2e^{-z} ≤ 2 max{1,z} is a template: for any routing-cover problem where a missed vertex can be attached for a constant C, the same sampling argument yields a factor of max{C, 1 + C/e}, suggesting where to look for improvements in other TSP variants.
  • Theorem 1.3 isolates the hard regime for the factor 2: the close-terminal case, where total source-sink distance is small, is exactly where the depot version must be improved to push Graphic Multi-Path TSP below 2.
  • The balancing of two Odd-joins suggests that other precedence-constrained routing problems might be attacked by identifying two cheap parity-correcting structures and optimizing their convex combination, rather than committing to one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper studies Graphic Multi-Path TSP and Graphic Ordered TSP. For Graphic Multi-Path TSP it gives a 2-approximation algorithm based on solving a flow LP, decomposing the flow into paths, sampling one path per commodity, and reconnecting uncovered vertices by doubled edges; the analysis is derandomized by conditional expectations. For Graphic Ordered TSP it gives a (1 + e/(2e-2))-approximation algorithm, using a single-edge reconnection followed by an Odd-join parity correction. The paper also proves a reduction showing that any below-2 approximation for Graphic Uncapacitated Multi-Depot VRP (the case s_i = t_i) would yield a below-2 approximation for Graphic Multi-Path TSP. A corollary of the main result is an integrality-gap upper bound of 2 for the proposed LP.

Significance. If the results hold, they improve the best known approximation ratios for two TSP variants in graphic metrics: from 2.214 to 2 for Graphic Multi-Path TSP and from 1.868 to 1.791 for Graphic Ordered TSP. The main algorithm is simple and the analysis is transparent, with an explicit derandomization argument. The paper also contains a conceptually interesting reduction connecting the general problem to the depot version. The central derivation for Theorem 1.1 is self-contained and appears sound, and the work gives a clean integrality-gap result for the LP.

minor comments (3)
  1. [Section 4, proof of Theorem 1.2] The step 'g(z)=z+(1+alpha)e^{-z} is convex and thus g(z) <= max{g(0), g(1)z}' is not a consequence of convexity alone; convexity does not imply that inequality for all z>=0. The inequality is true for this particular g, but a short proof should be supplied, for example by splitting into z<=1 and z>1 and using e^{-z} <= z/e for z>=1.
  2. [Section 5, proof of Theorem 1.3, Case 3.2] The inequality |V \ (S ∪ T ∪ V_P)| <= n - k is not valid when k > |S ∪ T|, e.g., for six distinct ordered pairs on three terminals. The correct bound is |V \ (S ∪ T)|, and the proof should use the fact |V \ (S ∪ T)| <= OPT(I), since every non-terminal vertex has degree at least 2 in the union of walks of any feasible solution. The argument goes through with this replacement.
  3. [Section 4, Algorithm 2, correctness] In the reconnection phase, adding only a single arc (v,w) to a walk F_i containing w does not by itself preserve the property that F_i is a walk from o_i to o_{i+1}. The correctness proof should explain why the final multigraph (∪_i F_i) ∪ J is a feasible Ordered TSP solution, e.g., by inserting the Eulerian components of the extra edges as closed detours into the cycle formed by the sampled paths, which preserves the prescribed terminal order.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 2-approximation is a self-contained LP-rounding analysis; citations to prior work are not load-bearing.

full rationale

I walked the derivation chain of Theorems 1.1-1.3. The LP is a relaxation: any integral solution maps to a feasible LP solution (Section 2), and the objective equals sum_v z_v. The algorithm samples paths from a flow decomposition with probabilities lambda; Eq. (8) is an accounting identity for the expected sampling cost via linearity, not a predetermination of the target bound. The reconnection probability bound e^{-zP_v} follows from independence across commodities and 1-x <= e^{-x}. The per-vertex inequality zP_v + 2e^{-zP_v} <= max(2, 2zP_v) is a numerical inequality, and summing with z_v >= 1 for non-terminals yields 2LP. There is no fitted parameter renamed as a prediction; the parameter alpha in Theorem 1.2 is chosen analytically to minimize a convex bound. The derandomization chooses the path minimizing expression (11) and preserves the invariant conditional expectation <= 2LP; this is the standard method of conditional expectations, not a restatement of the theorem. Citations to [6] (which shares an author) are used for the LP formulation being essentially equivalent and for the Odd-join containment y=1/2 x; both are prior published results and are not the target theorem. The latter, in the proof of Theorem 1.2, is terse but imports Wolsey's analysis, not an unverified self-citation. Section 5's reduction uses the 2-approximation of Algorithm 1 and a black-box VRP approximation; no quantity is fitted from the instance to manufacture the improved guarantee. The central claims are consequently derived from the LP and graph structure rather than being equivalent to their inputs. The only caveats are secondary correctness concerns (e.g., the terse Odd-join containment citation and the n-k <= OPT estimate in Case 3.2), which do not constitute circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper is an approximation-algorithm theory paper. It introduces no new entities and has no fitted parameters; all constants are chosen analytically. It relies on standard LP, flow decomposition, and odd-join machinery, plus the structural property of graphic metrics that reconnection costs are exactly 2 per uncovered vertex.

assumptions (5)
  • standard math LP (1)-(7) is a polynomial-time-solvable relaxation of Graphic Multi-Path TSP.
    Used throughout; separation of constraints (4) via min-cut, following Bohm et al. Feasibility is assumed without loss of generality.
  • standard math Any feasible single-commodity flow can be decomposed into at most |A| simple s-t paths and cycles, with path weights summing to 1.
    Invoked in Section 3 (Algorithm 1) and Section 4; standard flow decomposition (Schrijver, Combinatorial Optimization).
  • domain assumption For Ordered TSP, the LP solution satisfies the undirected cut condition x(delta(S)) >= 2 for all cuts, so y = x/2 lies in the Odd-join polytope.
    Used in Theorem 1.2; cited to Wolsey and Bohm et al. rather than proved. It follows from the cyclic terminal structure plus constraint (6), but the paper leaves this implicit.
  • standard math The Odd-join polytope is integral.
    Used in Theorem 1.2 to bound the smallest Odd-join by a fractional point; standard polyhedral result.
  • domain assumption Reconnecting a vertex by doubled arcs in a strongly connected bidirected graph costs exactly 2.
    Used in Lemma 3.2; relies on unit edge costs in the graphic metric and strong connectivity of G'.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating Graphic Multi-Path TSP and Graphic Ordered TSP." pith.science (2026). https://pith.science/paper/UO2N57XA

@misc{pith2026250900448,
  author       = {Pith},
  title        = {Pith review of: Approximating Graphic Multi-Path TSP and Graphic Ordered TSP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UO2N57XA}},
  note         = {Machine review of arXiv:2509.00448}
}
abstract

The path version of the Traveling Salesman Problem is one of the most well-studied variants of the ubiquitous TSP. Its generalization, the Multi-Path TSP, has recently been used in the best known algorithm for path TSP by Traub and Vygen [Cambridge University Press, 2024]. The best known approximation factor for this problem is $2.214$ by B\"{o}hm, Friggstad, M\"{o}mke and Spoerhase [SODA 2025]. In this paper we show that for the case of graphic metrics, a significantly better approximation guarantee of $2$ can be attained. Our algorithm is based on sampling paths from a decomposition of the flow corresponding to the optimal solution to the LP for the problem, and connecting the left-out vertices with doubled edges. The cost of the latter is twice the optimum in the worst case; we show how the cost of the sampled paths can be absorbed into it without increasing the approximation factor. Furthermore, we prove that any below-$2$ approximation algorithm for the special case of the problem where each source is the same as the corresponding sink yields a below-$2$ approximation algorithm for Graphic Multi-Path TSP. We also show that our ideas can be utilized to give a factor $1.791$-approximation algorithm for Ordered TSP in graphic metrics, for which the aforementioned paper [SODA 2025] and Armbruster, Mnich and N\"agele [APPROX 2024] give a $1.868$-approximation algorithm in general metrics.

Figures

Figures reproduced from arXiv: 2509.00448 by the authors.

Figure 1
Figure 1. The fractional solution in (b) of the instance in (a) has an objective function value of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Run of the algorithm on the instance of Figure [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

  1. [1]

    Approximating Prize-Collecting Variants of TSP

    Morteza Alimi, Tobias M¨ omke, and Michael Ruderer. Approximating prize-collecting variants of TSP. CoRR, abs/2411.14994, 2024

    work page Pith review arXiv 2024

  2. [2]

    A (3/2 + 1/ e)-approximation algorithm for ordered TSP

    Susanne Armbruster, Matthias Mnich, and Martin N¨ agele. A (3/2 + 1/ e)-approximation algorithm for ordered TSP. In APPROX/RANDOM, volume 317 of LIPIcs, pages 1:1–1:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

    work page 2024

  3. [3]

    Preserving and increasing local edge- connectivity in mixed graphs

    Jørgen Bang-Jensen, Andr´ as Frank, and Bill Jackson. Preserving and increasing local edge- connectivity in mixed graphs. SIAM Journal on Discrete Mathematics , 8(2):155–178, 1995

    work page 1995

  4. [4]

    A better-than-1.6-approximation for prize- collecting TSP

    Jannis Blauth, Nathan Klein, and Martin N¨ agele. A better-than-1.6-approximation for prize- collecting TSP. In IPCO, volume 14679 of Lecture Notes in Computer Science , pages 28–42. Springer, 2024

    work page 2024

  5. [5]

    An improved approximation guarantee for prize-collecting TSP

    Jannis Blauth and Martin N¨ agele. An improved approximation guarantee for prize-collecting TSP. In STOC, pages 1848–1861. ACM, 2023

    work page 2023

  6. [6]

    Approximating traveling salesman problems using a bridge lemma

    Martin B¨ ohm, Zachary Friggstad, Tobias M¨ omke, and Joachim Spoerhase. Approximating traveling salesman problems using a bridge lemma. In Proceedings of the 2025 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA) , pages 1166–1177. SIAM, 2025

    work page 2025

  7. [7]

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

    Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Operations Research Forum, 3, 1976. URL: https://api.semanticscholar.org/CorpusID: 123194397

    work page 1976

  8. [8]

    Compact, provably-good LPs for orienteering and regret-bounded vehicle routing

    Zachary Friggstad and Chaitanya Swamy. Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In IPCO, volume 10328 of Lecture Notes in Computer Science, pages 199–211. Springer, 2017

    work page 2017

Show all 19 references
  1. [9]

    A randomized rounding approach to the traveling salesman problem

    Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 550–559. IEEE, 2011. 16

    2011

  2. [10]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , STOC 2021, page 32–45, New York, NY, USA, 2021. Association for Computing Machin...

    2021

  3. [11]

    Approximating graphic TSP by matchings

    Tobias M¨ omke and Ola Svensson. Approximating graphic TSP by matchings. In 2011 IEEE 52nd annual symposium on foundations of computer science , pages 560–569. IEEE, 2011

    2011

  4. [12]

    13/9-approximation for graphic TSP

    Marcin Mucha. 13/9-approximation for graphic TSP. Theory of computing systems, 55(4):640– 657, 2014

    2014

  5. [13]

    Linear programming-based approximation algorithms for multi-vehicle minimum latency problems

    Ian Post and Chaitanya Swamy. Linear programming-based approximation algorithms for multi-vehicle minimum latency problems. In Proceedings of the Twenty-Sixth Annual ACM- SIAM Symposium on Discrete Algorithms , pages 512–531. SIAM, 2014

    2014

  6. [14]

    Combinatorial Optimization: Polyhedra and Efficiency , volume 24 of Algorithms and Combinatorics

    Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency , volume 24 of Algorithms and Combinatorics . Springer, 2003

    2003

  7. [15]

    Shorter tours by nicer ears: 7/5-approximation for the graph- TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

    Andr´ as Seb˝ o and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph- TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, pages 1–34, 2014

    2014

  8. [16]

    Serdjukov

    Alexander I. Serdjukov. Some extremal bypasses in graphs [in russian]. Upravlyaemye Sistemy, 17(89):76–79, 1978

    1978

  9. [17]

    Approximation Algorithms for Traveling Salesman Problems

    Vera Traub and Jens Vygen. Approximation Algorithms for Traveling Salesman Problems . Cambridge University Press, 2024

    2024

  10. [18]

    Reducing path TSP to TSP

    Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing path TSP to TSP. SIAM Journal on Computing, 51(3), 2021

    2021

  11. [19]

    Laurence A. Wolsey. Heuristic analysis, linear programming and branch and bound. In Com- binatorial Optimization II , volume 13 of Mathematical Programming Studies, pages 121–134. Springer, 1980. 17

    1980

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.