The integrality ratio of the standard LP relaxation for the metric s-t-path TSP

The metric $s$-$t$-path traveling salesman problem asks for a shortest Hamiltonian path with prescribed endpoints $s$ and $t$ in a finite metric space. Its standard LP relaxation — the Held–Karp subtour LP with unit demands on $s$-$t$-cuts — is conjectured to have integrality ratio exactly $3/2$, a value that simple unit-weight instances approach, yet the best proven upper bound is only $1.5273$. The gap is not due to lack of algorithmic progress: the problem admits a strongly polynomial $3/2$-approximation (Zenklusen, SODA 2019) and a $3/2+\varepsilon$ dynamic program (Traub–Vygen, JACM 2019), but neither algorithm is LP-relative — neither compares its output to the LP value — and the LP-relative analyses in the best-of-many Christofides lineage appear numerically saturated near $1.5273$. For the symmetric tour version, by contrast, the subtour LP gap is now known to be strictly below $3/2$. The problem is to determine the integrality ratio of the $s$-$t$-path LP: either prove that every instance admits an $s$-$t$-tour of cost at most $\frac{3}{2}$ times the LP optimum, or exhibit metric instances whose ratio is bounded away above $3/2$.

Background

An instance of the metric $s$-$t$-path TSP consists of a finite metric space $(V,c)$ — equivalently, the complete graph on $V$ with edge costs satisfying the triangle inequality — together with two vertices $s,t\in V$; the task is to find a minimum-cost Hamiltonian path with endpoints $s$ and $t$. For $s=t$ this is the classical (symmetric) metric TSP, for which Christofides' classical algorithm — take a minimum spanning tree, add a minimum-weight perfect matching on its odd-degree vertices, and shortcut the resulting Eulerian tour — still has the best known approximation ratio $3/2$.

The standard LP relaxation is the subtour LP (also called the Held–Karp relaxation): every tour crosses each cut at least twice, so incidence vectors of solutions satisfy $x(\delta(U))\ge 2$ for every nonempty proper vertex set $U$, where $\delta(U)$ denotes the set of edges with exactly one endpoint in $U$. For $s\ne t$ the natural adaptation weakens the requirement to $x(\delta(U))\ge 1$ across $s$-$t$-cuts (cuts separating $s$ from $t$); together with the degree constraints $x(\delta(v))=1$ for $v\in\{s,t\}$ and $x(\delta(v))=2$ otherwise, this is the LP whose integrality ratio is at issue (the degree-free version has the same optimal value by a classical splitting argument). The integrality ratio (integrality gap) of this LP is

$$\rho=\sup_{\text{instances }I}\frac{\mathrm{OPT}(I)}{\mathrm{OPT}_{LP}(I)},$$

the worst-case relative error committed by trusting the LP bound; an upper bound $\rho\le\alpha$ is exactly an LP-relative $\alpha$-approximation guarantee, i.e., an algorithm whose output is always within a factor $\alpha$ of the LP value (and hence of the optimum).

Wolsey's classical analysis shows $\rho\le 3/2$ when $s=t$: half of an optimal LP solution lies in the $T$-join polyhedron, where a $T$-join is an edge set whose odd-degree vertices are precisely a prescribed set $T$, so the parity-correcting step of Christofides' algorithm costs at most half the LP value. For $s\ne t$ this argument fails on narrow cuts — $s$-$t$-cuts $\delta(U)$ with LP value $x(\delta(U))<2$. Hoogeveen's path adaptation of Christofides' algorithm therefore achieves only $5/3$, and the integrality ratio of the path LP became a focal open question when An, Kleinberg, and Shmoys proved that the narrow cuts of any LP solution form a chain (a nested family) and improved the LP-relative bound to $1.618$. The subsequent chain of LP-relative improvements reads $5/3$ (Hoogeveen, 1991), $1.618$ (An–Kleinberg–Shmoys, 2015), $8/5$ (Sebő, 2013), $1.599$ (Vygen, 2016), $1.566$ (Gottschalk–Vygen, 2018), $3/2+1/34\approx 1.5294$ (Sebő–van Zuylen, 2019, via best-of-many Christofides with lonely-edge deletion: sample spanning trees from a convex decomposition of the LP solution, delete the lonely edges — those that are the only tree edge in a narrow cut — and repair parity), and finally $1.5284$ (Traub–Vygen, 2019) and $1.5273$ (Zhong, 2020), the current record, obtained by re-analyzing the Sebő–van Zuylen algorithm with a nearly optimal auxiliary function; numerical evidence indicates that this analysis framework cannot go substantially below $1.5273$.

On the other side, simple examples — including unit-weight instances — push the ratio to $3/2$, and the conjectured exact value is $3/2$. The approximation problem itself has in the meantime been settled: Traub and Vygen's recursive dynamic program attains $3/2+\varepsilon$ for any fixed $\varepsilon>0$, and Zenklusen's later algorithm attains exactly $3/2$ in strongly polynomial time; but neither is LP-relative — neither compares its output to the LP value — so both leave $\rho$ untouched. The contrast with the symmetric case is instructive: there, Karlin, Klein, and Oveis Gharan (FOCS 2022) proved the subtour LP gap is at most $3/2-\varepsilon$ via max-entropy rounding (rounding with the entropy-maximizing distribution over spanning trees consistent with the LP solution), whereas for the path LP even an LP-relative $3/2$ is open. In the graphic special case — metrics arising as shortest-path distances in an unweighted graph — the ratio is known to be exactly $3/2$ (Sebő–Vygen, 2014; Gao, 2013 gave an explicit LP-based $3/2$ for graphic $s$-$t$ paths), so a gap above $3/2$ in the general metric case, if one exists, must be witnessed by genuinely non-graphical metrics.

Problem Statement

Determine the integrality ratio $\rho$ of the standard LP relaxation of the metric $s$-$t$-path TSP; in particular, decide whether $\rho=\frac{3}{2}$ (the conjectured value) or $\rho>\frac{3}{2}$.

The LP is the following (the degree-constrained variant has the same optimal value). For a finite metric $(V,c)$ with distinct vertices $s,t\in V$, $s\ne t$, over $x\in\mathbb{R}_{\ge 0}^{E}$, where $E$ is the edge set of the complete graph on $V$; here $x(F):=\sum_{e\in F}x_e$ for a set $F\subseteq E$ of edges and $\delta(U)$ denotes the set of edges with exactly one endpoint in $U$:

$$\begin{aligned} \min\ & \sum_{e\in E} c_e x_e\\ \text{s.t.}\ & x(\delta(U))\ge 2 && \text{for } \emptyset\ne U\subseteq V\setminus\{s,t\},\\ & x(\delta(U))\ge 1 && \text{for } \{s\}\subseteq U\subseteq V\setminus\{t\},\\ & x_e\ge 0 && \text{for } e\in E. \end{aligned}$$

Here an $s$-$t$-tour is a Hamiltonian path with endpoints $s$ and $t$, $\mathrm{OPT}(I)$ is the minimum cost of an $s$-$t$-tour on instance $I$, $\mathrm{OPT}_{LP}(I)$ is the LP optimum, and $\rho=\sup_{I}\mathrm{OPT}(I)/\mathrm{OPT}_{LP}(I)$ over all instances of the metric $s$-$t$-path TSP (all finite metrics with all choices of distinct endpoints).

The question splits into the two branches $\rho=\frac{3}{2}$ and $\rho>\frac{3}{2}$. The equality $\rho=\frac{3}{2}$ is equivalent to every instance admitting an $s$-$t$-tour of cost at most $\frac{3}{2}\,\mathrm{OPT}_{LP}$. The strict inequality $\rho>\frac{3}{2}$ is equivalent to the existence of $\delta>0$ and metric instances with certified $\mathrm{OPT}/\mathrm{OPT}_{LP}\ge\frac{3}{2}+\delta$; since $\rho$ is a supremum over instances, a single certified metric instance with ratio strictly above $\frac{3}{2}$ refutes $\rho=\frac{3}{2}$. If $\rho>\frac{3}{2}$, the exact value is some $\rho=c$ with $c\in(\frac{3}{2},1.5273]$.

Currently known: $\frac{3}{2}\le\rho\le 1.5273$.

References

1. Vera Traub and Jens Vygen. Approaching 3/2 for the s-t-path TSP. Journal of the ACM 66(2) (2019), Article 14. DOI: 10.1145/3309715, https://doi.org/10.1145/3309715 (arXiv:1707.03992, https://arxiv.org/abs/1707.03992).
2. Vera Traub and Jens Vygen. An improved upper bound on the integrality ratio for the s-t-path TSP. Operations Research Letters 47(3) (2019), 225–228. DOI: 10.1016/j.orl.2019.02.005, https://doi.org/10.1016/j.orl.2019.02.005 (arXiv:1808.10734, https://arxiv.org/abs/1808.10734).
3. Xianghui Zhong. Slightly improved upper bound on the integrality ratio for the s-t Path TSP. Operations Research Letters 48(5) (2020), 627–629. DOI: 10.1016/j.orl.2020.07.015, https://doi.org/10.1016/j.orl.2020.07.015 (arXiv:2004.07217, https://arxiv.org/abs/2004.07217).
4. András Sebő and Anke van Zuylen. The Salesman's Improved Paths through Forests. Journal of the ACM 66(4) (2019), Article 28. DOI: 10.1145/3326123, https://doi.org/10.1145/3326123 (preprint: arXiv:1604.02486, https://arxiv.org/abs/1604.02486, titled 'The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio').
5. Rico Zenklusen. A 1.5-Approximation for Path TSP. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), SIAM, 1539–1549. DOI: 10.1137/1.9781611975482.93, https://doi.org/10.1137/1.9781611975482.93 (arXiv:1805.04131, https://arxiv.org/abs/1805.04131).
6. Hyung-Chan An, Robert Kleinberg, and David B. Shmoys. Improving Christofides' Algorithm for the s-t Path TSP. Journal of the ACM 62(5) (2015), Article 34. DOI: 10.1145/2818310, https://doi.org/10.1145/2818310 (arXiv:1110.4604, https://arxiv.org/abs/1110.4604).
7. J. A. Hoogeveen. Analysis of Christofides' heuristic: some paths are more difficult than cycles. Operations Research Letters 10(5) (1991), 291–295. DOI: 10.1016/0167-6377(91)90016-I, https://doi.org/10.1016/0167-6377(91)90016-I.
8. András Sebő. Eight-Fifth Approximation for the Path TSP. Integer Programming and Combinatorial Optimization (IPCO 2013), Lecture Notes in Computer Science 7801, Springer, 362–374. DOI: 10.1007/978-3-642-36694-9_31, https://doi.org/10.1007/978-3-642-36694-9_31.
9. Jens Vygen. Reassembling Trees for the Traveling Salesman. SIAM Journal on Discrete Mathematics 30(2) (2016), 875–894. DOI: 10.1137/15M1010531, https://doi.org/10.1137/15M1010531.
10. Corinna Gottschalk and Jens Vygen. Better s-t-tours by Gao trees. Mathematical Programming 172(1–2) (2018), 191–207. DOI: 10.1007/s10107-017-1202-z, https://doi.org/10.1007/s10107-017-1202-z (arXiv:1511.05514, https://arxiv.org/abs/1511.05514).
11. Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing Path TSP to TSP. SIAM Journal on Computing 51(3) (2022), STOC20-24–STOC20-53. DOI: 10.1137/20M135594X, https://doi.org/10.1137/20M135594X (arXiv:1907.10376, https://arxiv.org/abs/1907.10376).
12. Anna Karlin, Nathan Klein, and Shayan Oveis Gharan. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022), IEEE, 832–843. DOI: 10.1109/FOCS54457.2022.00084, https://doi.org/10.1109/FOCS54457.2022.00084 (arXiv:2105.10043, https://arxiv.org/abs/2105.10043).
13. András Sebő 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 34(5) (2014), 597–629. DOI: 10.1007/s00493-014-2960-3, https://doi.org/10.1007/s00493-014-2960-3.
14. Zhihan Gao. An LP-based 3/2-approximation algorithm for the s-t path graph Traveling Salesman Problem. Operations Research Letters 41(6) (2013), 615–617. DOI: 10.1016/j.orl.2013.08.006, https://doi.org/10.1016/j.orl.2013.08.006.
15. L. A. Wolsey. Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study 13 (1980), 121–134. DOI: 10.1007/BFb0120913, https://doi.org/10.1007/BFb0120913.
16. Michael Held and Richard M. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees. Operations Research 18(6) (1970), 1138–1162. DOI: 10.1287/opre.18.6.1138, https://doi.org/10.1287/opre.18.6.1138.
17. Vera Traub. Improving on Best-of-Many-Christofides for T-tours. Operations Research Letters 48(6) (2020), 798–804. DOI: 10.1016/j.orl.2020.09.009, https://doi.org/10.1016/j.orl.2020.09.009.
18. Martin Nägele and Rico Zenklusen. A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond. Mathematics of Operations Research 49(4) (2024), 2078–2108. DOI: 10.1287/moor.2023.0012, https://doi.org/10.1287/moor.2023.0012 (arXiv:2301.09340, https://arxiv.org/abs/2301.09340).
19. Xianghui Zhong. Lower Bounds on the Integraliy Ratio of the Subtour LP for the Traveling Salesman Problem. Preprint, arXiv:2102.04765 (2021), https://arxiv.org/abs/2102.04765 (title reproduced as on arXiv).
20. Vera Traub and Jens Vygen. Symmetric Path TSP and T-Tours, chapter (pp. 303–323) of: Approximation Algorithms for Traveling Salesman Problems, Cambridge University Press (2024). DOI: 10.1017/9781009445436.015, https://doi.org/10.1017/9781009445436.015.
21. Kristóf Bérczi, Matthias Mnich, and Roland Vincze. A 3/2-Approximation for the Metric Many-visits Path TSP. SIAM Journal on Discrete Mathematics 36(4) (2022), 2995–3030. DOI: 10.1137/22M1483414, https://doi.org/10.1137/22M1483414 (arXiv:2007.11389, https://arxiv.org/abs/2007.11389).
22. Junho Hwang. A 5/4 bound for graphic s-t path TSP on subcubic graphs. Preprint, arXiv:2608.11038 (2026), https://arxiv.org/abs/2608.11038.