In the metric s-t path traveling salesman problem (Path TSP), one must find a shortest Hamiltonian path with prescribed distinct endpoints s and t in a complete graph whose edge costs satisfy the triangle inequality. The natural linear programming relaxation - the Held-Karp (subtour) LP adapted to s-t paths - has integrality ratio known to lie between 3/2 and 1.5273 and conjectured to be exactly 3/2. The question of whether the approximation factor for Path TSP can be improved below 3/2 has since been resolved affirmatively: a black-box reduction from Path TSP to TSP (Traub-Vygen-Zenklusen, 2020) combined with the randomized 3/2-epsilon algorithm for metric TSP of Karlin-Klein-Oveis Gharan (2020, derandomized 2022) yields a 3/2-epsilon-approximation for Path TSP. The open problem is to determine the exact integrality ratio of the standard s-t path LP: either prove that it equals 3/2, matching the known instances that attain 3/2 asymptotically, or refute the conjecture by exhibiting instances whose ratio exceeds 3/2. The best proven upper bound is 1.5273 (Zhong, 2020).

Background

The traveling salesman problem (TSP) asks for a shortest closed tour visiting every vertex of a complete graph with nonnegative edge costs; in the metric version the costs satisfy the triangle inequality. The path version, usually called the s-t path TSP or Path TSP, asks instead for a shortest Hamiltonian path - a path visiting every vertex exactly once - whose two endpoints are two prescribed distinct vertices s and t. An alpha-approximation is a polynomial-time algorithm guaranteed to return a solution of cost at most alpha times the optimum; any alpha-approximation for Path TSP implies an alpha-approximation for the tour version, so the path problem is at least as hard to approximate.

Christofides' algorithm for metric TSP computes a minimum spanning tree and adds a minimum-cost matching on its odd-degree vertices, achieving ratio 3/2. Wolsey's analysis of this algorithm is relative to the Held-Karp relaxation (also called the subtour LP): the linear program that minimizes total cost subject to x(δ(v)) = 2 at every vertex and x(δ(U)) >= 2 for every nonempty proper vertex set U, where δ(U) denotes the set of edges with exactly one endpoint in U and x(δ(U)) the sum of the edge variables in that set. This proves the integrality ratio of the tour relaxation is at most 3/2, where the integrality ratio of a relaxation is the supremum, over all instances, of the ratio between the true optimum and the LP optimum; the ratio measures how weak the LP is as a lower bound. For the tour version the ratio is known to lie between 4/3 and 3/2, and since 2021 strictly below 3/2 (Karlin, Klein, and Oveis Gharan).

For the s-t path version the analogous LP (Hoogeveen's relaxation) replaces the degree constraints by degree 1 at s and at t and degree 2 at every other vertex, and weakens the connectivity constraint to x(δ(U))≥1x(\delta(U)) \ge 1 on cuts separating s from t. Christofides' idea extends (parity correction is done with a minimum-cost T-join, an edge set whose odd-degree vertices are exactly the vertices of wrong parity in the tree together with s and t), but Hoogeveen proved in 1991 that the resulting ratio is 5/3, and this is tight for the algorithm. Wolsey's argument fails because of narrow cuts: sets U separating s from t with x(δ(U))<2x(\delta(U)) < 2, on which the LP separates only by 1. An, Kleinberg, and Shmoys (2015) showed that the narrow cuts of an optimal LP solution form a chain under inclusion, and used this to build the best-of-many Christofides algorithm - decompose an optimal LP solution into a convex combination of spanning trees, run parity correction on each tree, and keep the cheapest result - achieving ratio (1+sqrt(5))/2, later refined by Sebő and van Zuylen (2016) to 3/2 + 1/34 by additionally deleting from each tree the lonely edges of narrow cuts (edges alone in a low-weight narrow cut) before parity correction. On the purely algorithmic side, Traub and Vygen (2019) reached 3/2 + epsilon for any fixed epsilon > 0, and Zenklusen (2019) reached 1.5, matching Christofides' tour bound - but, as Zenklusen highlights, these analyses are relative to the optimum and not to the LP, so they say nothing about the LP's integrality ratio.

The LP-relative lineage is therefore separate and slower: Hoogeveen's 5/3, An-Kleinberg-Shmoys's 1.618, Sebő-van Zuylen's 3/2+1/34 (approximately 1.5294), then Traub and Vygen's improved analysis of best-of-many Christofides with lonely-edge deletion giving 1.5284 (Operations Research Letters, 2019), and Zhong's near-optimal choice of the auxiliary function in that analysis giving 1.5273 (Operations Research Letters, 2020). Traub and Vygen's own numerical computations indicate that about 1.5273 is the best bound this framework can yield. On the other side, simple instance families - already implicit in the work of An, Kleinberg, and Shmoys - make the ratio of true optimum to LP optimum arbitrarily close to 3/2 from below. Hence the integrality ratio ρ⋆\rho^\star of the s-t path LP satisfies 3/2≤ρ⋆≤1.52733/2 \le \rho^\star \le 1.5273, and the long-standing conjecture is that ρ⋆=3/2\rho^\star = 3/2 exactly.

Two recent developments close the other half of the source question and sharpen the contrast. Traub, Vygen, and Zenklusen (STOC 2020) gave a black-box reduction showing that any alpha-approximation for metric TSP implies an (alpha+epsilon)-approximation for Path TSP, for any fixed epsilon > 0; combined with the randomized 3/2 - epsilon algorithm for metric TSP of Karlin, Klein, and Oveis Gharan (epsilon > 10^{-36}, derandomized in 2022), this yields a 3/2 - epsilon-approximation for the metric s-t path TSP, settling that Path TSP can be approximated below 3/2. The same authors also proved that the subtour LP gap for the tour version is at most 3/2 - epsilon, using their max-entropy algorithm, which samples a spanning tree from a maximum-entropy distribution consistent with the LP solution. No analogous result exists for the s-t path LP: its degree-1 constraints at s and t and its 1-separated s-t cuts change the polyhedral structure that the max-entropy analysis exploits, and the exact integrality ratio of this LP remains undetermined.

Problem Statement

Determine the exact integrality ratio ρ⋆\rho^\star of the standard LP relaxation for the metric s-t path TSP (the Held-Karp, or subtour, relaxation adapted to s-t paths). An instance is given by a finite metric space (V,c)(V, c) with distinct vertices s,t∈Vs, t \in V; the LP, over the edge set of the complete graph on VV, is

min⁡∑ec(e) x(e)\min \sum_{e} c(e)\, x(e) x(δ(U))≥2for ∅≠U⊆V∖{s,t}x(\delta(U)) \ge 2 \quad \text{for } \emptyset \ne U \subseteq V \setminus \{s, t\} x(δ(U))≥1for {s}⊆U⊆V∖{t}x(\delta(U)) \ge 1 \quad \text{for } \{s\} \subseteq U \subseteq V \setminus \{t\} x(δ(v))=2for v∈V∖{s,t},x(δ(s))=x(δ(t))=1x(\delta(v)) = 2 \quad \text{for } v \in V \setminus \{s, t\}, \qquad x(\delta(s)) = x(\delta(t)) = 1 x(e)≥0for every edge e,x(e) \ge 0 \quad \text{for every edge } e,

where δ(U)\delta(U) is the set of edges with exactly one endpoint in UU. Let LP(I)\mathrm{LP}(I) denote its optimum and OPT(I)\mathrm{OPT}(I) the minimum cost of a Hamiltonian path from ss to tt; the integrality ratio is ρ⋆=sup⁡IOPT(I)/LP(I)\rho^\star = \sup_{I} \mathrm{OPT}(I) / \mathrm{LP}(I) over all finite metric instances. It is known that 3/2≤ρ⋆≤1.52733/2 \le \rho^\star \le 1.5273, and the conjecture is that ρ⋆=3/2\rho^\star = 3/2. Resolve this question: either prove that OPT(I)≤32LP(I)\mathrm{OPT}(I) \le \frac{3}{2} \mathrm{LP}(I) for every finite metric instance, which together with the known instances whose ratio approaches 3/2 from below establishes ρ⋆=3/2\rho^\star = 3/2; or refute the conjecture by exhibiting an instance (or family of instances) with OPT(I)/LP(I)>3/2\mathrm{OPT}(I) / \mathrm{LP}(I) > 3/2.

References

  1. Rico Zenklusen, 'A 1.5-Approximation for Path TSP', Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) / arXiv:1805.04131, 2018, doi:10.48550/arXiv.1805.04131, https://arxiv.org/abs/1805.04131
  2. J. A. Hoogeveen, 'Analysis of Christofides' heuristic: Some paths are more difficult than cycles', Operations Research Letters 10(5), 1991, doi:10.1016/0167-6377(91)90016-I, https://doi.org/10.1016/0167-6377(91)90016-I
  3. Hyung-Chan An, Robert Kleinberg, David B. Shmoys, 'Improving Christofides' Algorithm for the s-t Path TSP', Journal of the ACM 62(5), 2015, doi:10.1145/2818310, https://doi.org/10.1145/2818310
  4. András Sebő, Anke van Zuylen, 'The Salesman's Improved Paths: A 3/2+1/34 Approximation', Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016), 2016, doi:10.1109/FOCS.2016.21, https://doi.org/10.1109/FOCS.2016.21
  5. Vera Traub, Jens Vygen, 'Approaching 3/2 for the s-t-path TSP', Journal of the ACM, 2019, arXiv:1707.03992, doi:10.1145/3309715, https://doi.org/10.1145/3309715
  6. Vera Traub, Jens Vygen, 'An improved upper bound on the integrality ratio for the s-t-path TSP', Operations Research Letters, 2019, arXiv:1808.10734, doi:10.1016/j.orl.2019.02.005, https://doi.org/10.1016/j.orl.2019.02.005
  7. Vera Traub, Jens Vygen, Rico Zenklusen, 'Reducing Path TSP to TSP', Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020) / SIAM Journal on Computing, 2022, arXiv:1907.10376, doi:10.48550/arXiv.1907.10376, https://arxiv.org/abs/1907.10376
  8. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Approximation Algorithm for Metric TSP', 2020, arXiv:2007.01409, doi:10.48550/arXiv.2007.01409, https://arxiv.org/abs/2007.01409
  9. Anna Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP', 2021, arXiv:2105.10043, doi:10.48550/arXiv.2105.10043, https://arxiv.org/abs/2105.10043
  10. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP', 2022, arXiv:2212.06296, doi:10.48550/arXiv.2212.06296, https://arxiv.org/abs/2212.06296
  11. Xianghui Zhong, 'Slightly improved upper bound on the integrality ratio for the s-t Path TSP', Operations Research Letters, 2020, arXiv:2004.07217, doi:10.1016/j.orl.2020.07.015, https://doi.org/10.1016/j.orl.2020.07.015
  12. Sophia Saller, Jana Koehler, Andreas Karrenbauer, 'A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme', 2023, arXiv:2311.00604, doi:10.48550/arXiv.2311.00604, https://arxiv.org/abs/2311.00604
  13. Vera Traub, 'Improving on Best-of-Many-Christofides for T-tours', 2020, arXiv:2009.09743, doi:10.48550/arXiv.2009.09743, https://arxiv.org/abs/2009.09743