pith. sign in

arxiv: 1907.10376 · v1 · pith:C4A7FU2Snew · submitted 2019-07-24 · 💻 cs.DM · cs.DS· math.CO

Reducing Path TSP to TSP

Vera Traub , Jens Vygen , Rico Zenklusen This is my paper

Pith reviewed 2026-05-24 16:36 UTC · model grok-4.3

classification 💻 cs.DM cs.DSmath.CO
keywords Path TSPTSP approximationblack-box reductiondynamic programmingGraph TSPparity constraintsconnectivity requirements
0
0 comments X

The pith

Given any α-approximation algorithm for TSP, one can build an (α + ε)-approximation algorithm for Path TSP for every ε > 0.

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

The paper shows how to reduce the path version of the traveling salesman problem to the standard tour version while losing only an arbitrarily small amount in the approximation factor. A sympathetic reader would care because this makes the two problems equivalent in approximability, ending earlier situations where the best known factors differed. The argument relies on a recursive dynamic program that guesses large pieces of an optimal path solution and on an auxiliary problem called Φ-TSP that combines parity and connectivity constraints. When the dynamic program stalls, Φ-TSP is reduced back to ordinary TSP. The same reduction applies directly to the unit-weight Graph TSP case.

Core claim

There exists a black-box reduction showing that an α-approximation algorithm for TSP yields an (α + ε)-approximation algorithm for Path TSP for any ε > 0. The reduction proceeds by recursively guessing significant segments of an optimal solution via dynamic programming; at its core it solves instances of a new generalization Φ-TSP that enforces both parity constraints and connectivity requirements, and it reduces those instances to TSP whenever the dynamic program fails to make sufficient progress.

What carries the argument

A recursive dynamic program that guesses significant parts of an optimal solution, together with the auxiliary problem Φ-TSP that merges parity constraints with connectivity requirements.

If this is right

  • The best approximation factor achievable for Path TSP is identical to that for TSP, up to an arbitrarily small additive term.
  • A 1.4-approximation for Graph TSP immediately yields a (1.4 + ε)-approximation for Graph Path TSP.
  • Future improvements to TSP approximations translate automatically to Path TSP without separate case analysis.

Where Pith is reading between the lines

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

  • The same guessing technique could be tested on other TSP variants that add parity or connectivity side constraints.
  • If the reduction can be derandomized or made fully polynomial, it would give a direct way to transfer exact algorithms as well.
  • The existence of Φ-TSP as an intermediate problem suggests that other hybrid TSP problems with mixed constraints might also reduce to the plain version.

Load-bearing premise

The dynamic program is always able to guess enough of an optimal solution or else reduce the remaining instance to ordinary TSP via Φ-TSP.

What would settle it

An explicit Path TSP instance together with an α-approximate TSP oracle such that every output of the reduction has cost strictly larger than (α + ε) times the optimum for some fixed ε.

Figures

Figures reproduced from arXiv: 1907.10376 by Jens Vygen, Rico Zenklusen, Vera Traub.

Figure 1
Figure 1. Figure 1: Illustration of an optimal solution OPT of a Graph Path TSP instance with 9 = d(s, t) > 1/3·|OPT| = 23/3. Thick blue edges are OPT-edges that are the only one in some cut δ(Li). Knowing these edges, the problem breaks into six smaller instances: a trivial s-u0 Path TSP problem in G[L0], one v0-u2 Path TSP problem in G[L2 \ L0] and so on, with the last instance being a trivial v8-t Path TSP problem in G[V \… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration for guessing edges in cuts δ(Li) that contain at most five OPT-edges. In this example, δ(L0), δ(L1), and δ(L3) are these cuts and the edges crossing them are highlighted as thick blue edges. We now define a sub-problem in G[L3 \ L1]. We call the endpoints of the thick blue edges interface vertices (red). The gray sets show the connectivity requirements on the interfaces vertices in this sub-pr… view at source ↗
Figure 3
Figure 3. Figure 3: exemplifies the notation of an interface Φ and a Φ-tour. : T C1 C2 C3 C4 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: On the left-hand side, an interface Φ = (I, T, C) on a graph G = (V, E) is shown together with a Φ-tour F ⊆ E (the black edges) and a set W ⊆ V . The right-hand side figure depicts the interface ΦW = (IW , TW , CW ) induced by (F, Φ) on W. This implies, together with IW = (I ∩ W) ∪ U—which holds by definition of IW —that W′ ⊆ V \ I with W′ 6= V and F ∩ δ(W′ ) = F[W] ∩ δ(W′ ) = ∅. This contradicts the fact … view at source ↗
Figure 5
Figure 5. Figure 5: The dashed ellipsoids show the partition of V into W0, . . . , Wp. The thick blue edges are the edges in X. Only the vertices in ¯I are shown here, where the vertices with a red boundary are those contained in I. Lemma 22. Let G = (V, E, ℓ) be a weighted graph. Let Φ = (I, T, C) be an interface of G and let F be a Φ-tour in G. Let W0, . . . , Wp be a partition of V . For i ∈ {0, . . . , p}, let Φi = (Ii , … view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of Algorithm 4. The dashed ellipses show the laminar family L; these sets are considered by the algorithm in an order of non-decreasing cardinality. Suppose we are considering L ∈ L(R, k); only subsets of L are shown in the figure. In the dynamic program we guess the children L1, . . . , Lp of L in the laminar family L(R, k). The sets L1, . . . , Lp are shown as blue ellipses with white interi… view at source ↗
read the original abstract

We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an $\alpha$-approximation algorithm for TSP, then, for any $\epsilon >0$, there is an $(\alpha+\epsilon)$-approximation algorithm for the more general Path TSP. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error. This avoids future discrepancies between the best known approximation factors achievable for these two problems, as they have existed until very recently. A well-studied special case of TSP, Graph TSP, asks for tours in unit-weight graphs. Our reduction shows that any $\alpha$-approximation algorithm for Graph TSP implies an $(\alpha+\epsilon)$-approximation algorithm for its path version. By applying our reduction to the $1.4$-approximation algorithm for Graph TSP by Seb\H{o} and Vygen, we obtain a polynomial-time $(1.4+\epsilon)$-approximation algorithm for Graph Path TSP, improving on a recent $1.497$-approximation algorithm of Traub and Vygen. We obtain our results through a variety of new techniques, including a novel way to set up a recursive dynamic program to guess significant parts of an optimal solution. At the core of our dynamic program we deal with instances of a new generalization of (Path) TSP which combines parity constraints with certain connectivity requirements. This problem, which we call $\Phi$-TSP, has a constant-factor approximation algorithm and can be reduced to TSP in certain cases when the dynamic program would not make sufficient progress.

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 / 1 minor

Summary. The paper claims a black-box reduction from Path TSP to TSP: given any α-approximation algorithm for TSP, for every ε > 0 there exists an (α + ε)-approximation algorithm for Path TSP. The reduction is realized by a novel recursive dynamic program that guesses significant portions of an optimal solution; at its core is a new generalization Φ-TSP that combines parity constraints with connectivity requirements. Φ-TSP is shown to admit a constant-factor approximation and, in certain cases, to reduce directly to TSP when the DP makes insufficient progress. The same reduction applies to Graph TSP, yielding a (1.4 + ε)-approximation for Graph Path TSP from the known 1.4-approximation of Sebő and Vygen.

Significance. If the reduction and its ratio analysis hold, the result equates the approximability of Path TSP with that of TSP up to an arbitrarily small additive error, eliminating the possibility of future gaps between the two problems. It also immediately improves the best known approximation for Graph Path TSP. The introduction of the Φ-TSP generalization and the recursive DP technique constitute the main technical novelty.

major comments (2)
  1. [Abstract / recursive DP analysis] Abstract and the description of the recursive DP: the overall (α + ε) guarantee relies on partitioning the recursion into progress and non-progress branches. In non-progress branches the algorithm either reduces directly to TSP or invokes the constant-factor approximation for Φ-TSP. The manuscript must contain an explicit calculation (presumably in the section analyzing the approximation ratio of the DP) showing that any invocation of the Φ-TSP routine contributes at most an ε-fraction of the total cost for every α and every sufficiently small ε; otherwise the black-box claim does not hold.
  2. [Definition of Φ-TSP and its approximation algorithm] The definition and approximation algorithm for Φ-TSP (core of the dynamic program): because Φ-TSP is a new problem invented for the reduction, the constant-factor guarantee must be shown to be independent of α. If the constant depends on α, the partition argument required by the previous comment cannot be carried out for arbitrary α.
minor comments (1)
  1. [Abstract] The abstract states that Φ-TSP “can be reduced to TSP in certain cases”; the precise conditions under which this reduction is possible should be stated explicitly in the main text, together with a reference to the relevant lemma or theorem.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments. We address each major comment below and are prepared to revise the paper to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Abstract / recursive DP analysis] Abstract and the description of the recursive DP: the overall (α + ε) guarantee relies on partitioning the recursion into progress and non-progress branches. In non-progress branches the algorithm either reduces directly to TSP or invokes the constant-factor approximation for Φ-TSP. The manuscript must contain an explicit calculation (presumably in the section analyzing the approximation ratio of the DP) showing that any invocation of the Φ-TSP routine contributes at most an ε-fraction of the total cost for every α and every sufficiently small ε; otherwise the black-box claim does not hold.

    Authors: We agree that an explicit calculation is required to fully substantiate the black-box claim. While the current analysis in the recursive DP section partitions the recursion tree into progress and non-progress branches and handles the latter via either direct TSP reduction or the Φ-TSP routine, we acknowledge that the bounding of the Φ-TSP contribution relative to ε (for arbitrary α) is only sketched rather than computed in detail. In the revised manuscript we will add a dedicated paragraph (or short subsection) in the approximation-ratio analysis that explicitly chooses the progress threshold δ = Θ(ε) and recursion depth, then shows that the total additive cost from all Φ-TSP invocations is at most ε·OPT, independently of α. This will be placed immediately after the description of the non-progress case. revision: yes

  2. Referee: [Definition of Φ-TSP and its approximation algorithm] The definition and approximation algorithm for Φ-TSP (core of the dynamic program): because Φ-TSP is a new problem invented for the reduction, the constant-factor guarantee must be shown to be independent of α. If the constant depends on α, the partition argument required by the previous comment cannot be carried out for arbitrary α.

    Authors: The constant-factor approximation algorithm for Φ-TSP is independent of α. Φ-TSP is defined purely in terms of the input graph, the parity vector Φ, and the connectivity requirements; its formulation and the subsequent 4-approximation (via a combination of T-join and spanning-tree techniques) contain no reference to any TSP approximation factor. We will revise the manuscript to state this independence explicitly in the paragraph introducing the Φ-TSP approximation and to include a one-sentence remark confirming that the ratio is an absolute constant. This directly enables the partition argument to hold for every α. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation is a black-box reduction from Path TSP to TSP that invokes an external α-approximation for TSP and introduces an auxiliary Φ-TSP problem whose constant-factor approximation is developed as an independent subroutine within the same paper; neither the main claim nor the Φ-TSP guarantee reduces by construction to a fitted parameter, self-citation chain, or renamed input. The single self-citation to prior Traub-Vygen work is used only to contextualize an improvement and is not load-bearing for the reduction itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

The paper relies on standard assumptions in approximation algorithms such as the existence of α-approximation oracles for TSP; introduces Φ-TSP as a new problem variant without fitted parameters.

invented entities (1)
  • Φ-TSP no independent evidence
    purpose: A generalization of (Path) TSP combining parity constraints with connectivity requirements to facilitate the dynamic program reduction.
    Introduced as a technical tool in the paper; no independent evidence provided in abstract.

pith-pipeline@v0.9.0 · 5834 in / 1140 out tokens · 34248 ms · 2026-05-24T16:36:25.618735+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

31 extracted references · 31 canonical work pages

  1. [1]

    H.-C. An, R. Kleinberg, and D. B. Shmoys. Improving Chris tofides’ algorithm for the s-t path TSP. Journal of the ACM, 62(5):34:1–34:28, 2015. Short version appeared in STOC 20 12

    work page 2015

  2. [2]

    A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal on Computing, 37(2):653–670, 2007. Short version appeared in FOCS 2003

    work page 2007

  3. [3]

    Cheriyan, Z

    J. Cheriyan, Z. Friggstad, and Z. Gao. Approximating min imum-cost connected T -joins. Algorithmica, 72:126–147, 2015. Short version appeared in APPROX/RANDOM 2012

    work page 2015

  4. [4]

    Christofides

    N. Christofides. Worst-case analysis of a new heuristic f or the Travelling Salesman Problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976

    work page 1976

  5. [5]

    Eisenbrand

    F. Eisenbrand. Integer programming and algorithmic geo metry of numbers. In M. J¨ unger, T. M. Liebling, D. Naddef, G. L. Nemhauser, and W. R. Pulleyblank, editors, 50 Years of Integer Program- ming 1958–2008, pages 505–559. Springer, 2010

    work page 1958

  6. [6]

    Feige and M

    U. Feige and M. Singh. Improved approximation algorithm s for traveling salesperson tours and paths in directed graphs. In Proceedings of the 10th International Workshop on Approxim ation Algorithms for Combinatorial Optimization Problems (APPROX), pages 104–118, 2007

    work page 2007

  7. [7]

    Frank and ´E

    A. Frank and ´E. Tardos. An application of simultaneous diophantine appr oximation in combinatorial optimization. Combinatorica, 7(1):49–65, 1987

    work page 1987

  8. [8]

    Z. Gao. An LP-based 3 2 -approximation algorithm for the s-t path graph traveling salesman problem. Operations Research Letters, 41:615–617, 2013

    work page 2013

  9. [9]

    M. X. Goemans, A. V . Goldberg, S. Plotkin, D. B. Shmoys, ´E. Tardos, and D. P . Williamson. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 223–232, 1994

    work page 1994

  10. [10]

    Gottschalk and J

    C. Gottschalk and J. Vygen. Better s-t-tours by Gao trees. Mathematical Programming B, 172:191– 207, 2018. Short version appeared at IPCO 2016

    work page 2018

  11. [11]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization , volume 2 of Algorithms and Combinatorics. Springer, second corrected edition, 1993. 27

    work page 1993

  12. [12]

    Hoogeveen

    J.A. Hoogeveen. Analysis of Christofides’ heuristic: S ome paths are more difficult than cycles. Oper- ations Research Letters, 10(5):291–295, 1991

    work page 1991

  13. [13]

    K. Jain. A factor 2 approximation algorithm for the gene ralized Steiner Network Problem. Combina- torica, 21:39–60, 2001. Short version appeared in FOCS 1998

    work page 2001

  14. [14]

    Karpinski, M

    M. Karpinski, M. Lampis, and R. Schmied. New inapproxim ability bounds for TSP. Journal of Computer and System Sciences , 81:1665–1677, 2015. Short version appeared in ISAAC 2013

    work page 2015

  15. [15]

    A. V . Karzanov. How to tidy up a symmetric set-system by u se of uncrossing operations. Theoretical Computer Science, 157:215–225, 1996

    work page 1996

  16. [16]

    M¨ omke and O

    T. M¨ omke and O. Svensson. Removing and adding edges forthe Traveling Salesman Problem. Journal of the ACM, 63(1):2:1–2:28, 2016. Short version appeared in FOCS 2011

    work page 2016

  17. [17]

    M. Mucha. 13 9 -approximation for graphic TSP. Theory of Computing Systems , 55(4):640–657, 2014. Short version appeared in STACS 2012

    work page 2014

  18. [18]

    N¨ agele and R

    M. N¨ agele and R. Zenklusen. A new dynamic programming a pproach for spanning trees with chain constraints and beyond. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discre te Algo- rithms (SODA), pages 1550–1569, 2019

    work page 2019

  19. [19]

    Oveis Gharan, A

    S. Oveis Gharan, A. Saberi, and M. Singh. A randomized ro unding approach to the Traveling Salesman Problem. In Proceedings of the 52nd Annual IEEE Symposium on F oundation s of Computer Science (FOCS), pages 550–559, 2011

    work page 2011

  20. [20]

    C. H. Papadimitriou and M. Y annakakis. The Traveling Sa lesman Problem with distances one and two. Mathematics of Operations Research, 18(1):1–12, 1993

    work page 1993

  21. [21]

    Schrijver

    A. Schrijver. Combinatorial Optimization, Polyhedra and Efficiency. Springer, 2003

    work page 2003

  22. [22]

    A. Seb˝ o. Eight-fifth approximation for the Path TSP. In Proceedings of 16th International Conference on Integer Programming and Combinatorial Optimization (IP CO), pages 263–373, 2013

    work page 2013

  23. [23]

    Seb˝ o and A

    A. Seb˝ o and A. van Zuylen. The salesman’s improved path s through forests. Journal of the ACM , 66(4):28:1–28:16, 2019. Short version appeared in FOCS 201 6

    work page 2019

  24. [24]

    Seb˝ o and J

    A. Seb˝ o and J. Vygen. Shorter tours by nicer ears: 7/5-a pproximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597–629, 2014

    work page 2014

  25. [25]

    A. I. Serdjukov. Some extremal bypasses in graphs [in Ru ssian]. Upravlyaemye Sistemy, 17:76–79, 1978

    work page 1978

  26. [26]

    Traub and J

    V . Traub and J. Vygen. Beating the integrality ratio for s-t-tours in graphs. In Proceedings of 59th Annual IEEE Symposium on F oundations of Computer Science (FOCS), pages 766–777, 2018

    work page 2018

  27. [27]

    Traub and J

    V . Traub and J. Vygen. Approaching 3 2 for the s-t path TSP. Journal of the ACM , 66(2):14:1–14:17,

    work page

  28. [28]

    Short version appeared in SODA 2018

    work page 2018

  29. [29]

    J. Vygen. Reassembling trees for the traveling salesma n. SIAM Journal on Discrete Mathematics , 30(2):875–894, 2016

    work page 2016

  30. [30]

    Xu and B Rodrigues

    Z. Xu and B Rodrigues. A 3/2-approximation algorithm fo r the multiple TSP with a fixed number of depots. INFORMS Journal on Computing, 27(4):636–645, 2015. 28

    work page 2015

  31. [31]

    Zenklusen

    R. Zenklusen. A 1. 5-approximation for Path TSP. In Proceedings of 30th Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA) , pages 1539–1549, 2019. 29

    work page 2019