Is the integrality gap of the subtour-elimination LP for the metric s-t path TSP exactly 3/2?

The metric s-t path TSP asks for a shortest Hamiltonian path between two prescribed vertices of a finite metric space. Its standard relaxation is the subtour-elimination LP (the path version of the Held-Karp relaxation), whose optimum $OPT_{LP}$ lower-bounds the true optimum $OPT$; the integrality gap is the worst-case ratio $OPT/OPT_{LP}$. Simple example families force this ratio arbitrarily close to $3/2$, while the best known upper bound is 1.5273 (Zhong, 2020), obtained by refining the analysis of best-of-many Christofides-Serdyukov with lonely-edge deletion - the algorithm of Sebő and Van Zuylen (ratio $3/2+1/34$), as re-analyzed by Traub and Vygen ($<1.5284$). Zenklusen's polynomial-time 1.5-approximation is relative to $OPT$ and, as later work explicitly notes, implies no LP-relative bound. The open question, stated in the conclusion of Sebő and Van Zuylen's paper, is whether the integrality gap equals $3/2$: does every metric instance admit an $\{s,t\}$-tour of cost at most $(3/2)\cdot OPT_{LP}$ - and in particular, do best-of-many Christofides-Serdyukov, with or without lonely-edge deletion, never exceed $1.5\cdot OPT_{LP}$, for which no counterexample is known? A resolution is either a proof of the $3/2$ bound or an explicit instance with $OPT>(3/2)\cdot OPT_{LP}$.

Background

In the metric traveling salesman problem (TSP) one is given a finite metric space $(V,c)$ - a complete graph on vertex set $V$ whose edge costs $c$ are symmetric and satisfy the triangle inequality - and seeks a minimum-cost tour visiting every vertex. The s-t path TSP is the variant in which two distinct vertices $s,t\in V$ are prescribed and one seeks a shortest Hamiltonian path from $s$ to $t$. It is convenient to work with $\{s,t\}$-tours: multisets of edges forming a connected spanning multigraph in which exactly $s$ and $t$ have odd degree. An $\{s,t\}$-tour admits an Eulerian walk from $s$ to $t$, which can be shortcut to a Hamiltonian path of no larger cost by the triangle inequality, and conversely every Hamiltonian s-t path is an $\{s,t\}$-tour; hence the optimum $OPT$ equals the minimum cost of an $\{s,t\}$-tour.

The standard relaxation is the subtour-elimination LP (the path version of the Held-Karp relaxation): $\min \sum_{e} c_e x_e$ $x(\delta(v)) = 1 \ \text{for}\ v \in \{s,t\}, \qquad x(\delta(v)) = 2 \ \text{for}\ v \in V\setminus\{s,t\},$ $x(\delta(U)) \ge 2 \ \text{for}\ \emptyset \neq U \subseteq V\setminus\{s,t\}, \qquad x_e \ge 0,$ where $\delta(U)$ denotes the set of edges with exactly one endpoint in $U$ and $x(F)=\sum_{e\in F}x_e$. The LP has exponentially many constraints but is separable in polynomial time via minimum-cut computations. Its optimum $OPT_{LP}$ satisfies $OPT_{LP}\le OPT$, and the integrality gap is the supremum of $OPT/OPT_{LP}$ over all finite metric instances. For the tour version of metric TSP this gap is known to lie between $4/3$ and $3/2-\epsilon$ for some $\epsilon>10^{-36}$ (Karlin, Klein, and Oveis Gharan); for the path version studied here, simple example families force $OPT/OPT_{LP}$ arbitrarily close to $3/2$ (Traub and Vygen), so the gap is at least $3/2$, and the conjecture is that it equals $3/2$ exactly.

The algorithmic lineage is as follows. The Christofides-Serdyukov algorithm for the tour version computes a minimum spanning tree and adds a minimum-cost perfect matching on the odd-degree vertices, giving $3/2$. Hoogeveen adapted it to paths: given a spanning tree, correct the parity by adding a minimum-cost $T$-join (a set $J$ of edges whose odd-degree vertex set is exactly $T$) for the set $T$ of vertices whose degree parity in the tree differs from what an $\{s,t\}$-tour requires; this gives ratio $5/3$. An, Kleinberg, and Shmoys improved the ratio to the golden ratio $\varphi\approx 1.618$ by choosing the initial spanning tree from an optimal LP solution rather than from a minimum spanning tree; their analysis introduced narrow cuts - cuts $\delta(U)$ with $x^*(\delta(U))<2$, on which the classical LP-based analysis of the Christofides-Serdyukov routine fails - and showed that the narrow cuts of an LP solution form a chain. Sebő proved $8/5$ for the best-of-many version, in which the LP optimum $x^*$ is written as a convex combination of spanning trees (possible because $x^*$ itself lies in the spanning-tree polytope, as follows from the degree and cut constraints above, its total edge value being $|V|-1$), Hoogeveen's routine is run from each tree, and the best result is kept. Gottschalk and Vygen improved this to 1.566 (from the previous 1.599) by proving that the convex combination can be chosen so that many of its trees are Gao trees - spanning trees that contain exactly one edge of every narrow cut.

Sebő and Van Zuylen achieved $3/2+1/34\approx 1.5294$ relative to $OPT_{LP}$ with best-of-many Christofides-Serdyukov with deletion (BOMD): in each tree of the convex combination, the lonely edges (in each tree, the edges that are that tree's unique edge in some narrow cut) are deleted, the resulting forest is parity-corrected by a $T$-join, and the disconnected remains are reconnected at a separately bounded cost. Traub and Vygen re-analyzed the same algorithm and improved the bound to below $1.5284$, and Zhong optimized the auxiliary function in that analysis to obtain 1.5273, the best known upper bound on the integrality gap. On the side of the true optimum, Traub and Vygen gave a polynomial-time $(3/2+\epsilon)$-approximation for every fixed $\epsilon>0$ via dynamic programming over near-minimum cuts, and Zenklusen reached $3/2$ relative to $OPT$; Traub, Vygen, and Zenklusen later gave a black-box reduction from path TSP to TSP, which combined with the $(3/2-\epsilon)$-approximation for metric TSP of Karlin, Klein, and Oveis Gharan yields a randomized $(3/2-\delta)$-approximation relative to $OPT$. As Traub and Vygen explicitly note, none of these optimum-relative algorithms implies any upper bound on the integrality gap of the LP.

Thus the gap is pinned between $3/2$ and 1.5273. The conclusion of Sebő and Van Zuylen's paper states that the conjecture that the integrality gap is 1.5 is still open; that there is no counterexample to the conjecture that an $\{s,t\}$-tour of cost at most 1.5 times the LP bound can be reached by their algorithm, or even by the vanilla best-of-many Christofides-Serdyukov algorithm; and that the bottleneck of the analysis is the reconnection cost, for which they found a practical but not yet ideal treatment. They also observe that their extremal example certifying tightness of the analysis is not an extreme point of the LP polytope and that the fractional bounds used for parity plus reconnection need not be simultaneously tight for integer decompositions, so the analytical barrier may exceed the true performance of the algorithm.

Problem Statement

Let $(V,c)$ be a finite metric space - a complete graph on a finite vertex set $V$ whose edge costs $c$ are symmetric and satisfy the triangle inequality - and let $s,t\in V$ with $s\ne t$ be prescribed. An $\{s,t\}$-tour is a multiset of edges forming a connected spanning multigraph in which exactly the vertices $s$ and $t$ have odd degree; every $\{s,t\}$-tour has an Eulerian walk from $s$ to $t$ that can be shortcut, by the triangle inequality, to a Hamiltonian path from $s$ to $t$ (a path visiting every vertex exactly once) of no larger cost, and every Hamiltonian path from $s$ to $t$ is an $\{s,t\}$-tour. Hence the optimum of the s-t path TSP, denoted $OPT$, equals the minimum cost of an $\{s,t\}$-tour. Let $OPT_{LP}$ be the optimum of the subtour-elimination LP (the path version of the Held-Karp relaxation):

$\min \sum_{e} c_e x_e$ $x(\delta(v)) = 1 \ \text{for}\ v \in \{s,t\}, \qquad x(\delta(v)) = 2 \ \text{for}\ v \in V\setminus\{s,t\},$ $x(\delta(U)) \ge 2 \ \text{for}\ \emptyset \neq U \subseteq V\setminus\{s,t\}, \qquad x_e \ge 0,$

where $\delta(U)$ denotes the set of edges with exactly one endpoint in $U$ and $x(F)=\sum_{e\in F}x_e$. The integrality gap is the supremum of $OPT/OPT_{LP}$ over all finite metric instances with $s\ne t$; it is known to be at least $3/2$ (simple example families approach $3/2$) and at most 1.5273. The conjecture - stated as open in the conclusion of Sebő and Van Zuylen's paper - is that the gap equals $3/2$ exactly.

Decide this question: is $OPT\le(3/2)\cdot OPT_{LP}$ for every metric instance? Equivalently, does every metric instance admit an $\{s,t\}$-tour of cost at most $(3/2)\cdot OPT_{LP}$, or is there a metric instance with $OPT>(3/2)\cdot OPT_{LP}$?

References

1. András Sebő and Anke van Zuylen, The Salesman's Improved Paths through Forests, Journal of the ACM 66(4):1-16, 2019. 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')
2. J. A. Hoogeveen, Analysis of Christofides' heuristic: Some paths are more difficult than cycles, Operations Research Letters 10(5):291-295, 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, and David B. Shmoys, Improving Christofides' Algorithm for the s-t Path TSP, Journal of the ACM 62(5):1-28, 2015. DOI: 10.1145/2818310, https://doi.org/10.1145/2818310 (preprint arXiv:1110.4604, https://arxiv.org/abs/1110.4604)
4. András Sebő, Eight-Fifth Approximation for the Path TSP, in: Integer Programming and Combinatorial Optimization (IPCO 2013), Lecture Notes in Computer Science 7801, pp. 362-374, 2013. DOI: 10.1007/978-3-642-36694-9_31, https://doi.org/10.1007/978-3-642-36694-9_31 (preprint arXiv:1209.3523, https://arxiv.org/abs/1209.3523, titled 'Eight-Fifth Approximation for TSP Paths')
5. Corinna Gottschalk and Jens Vygen, Better s-t-tours by Gao trees, Mathematical Programming 172(1-2):191-207, 2018 (published online 2017). DOI: 10.1007/s10107-017-1202-z, https://doi.org/10.1007/s10107-017-1202-z (preprint arXiv:1511.05514, https://arxiv.org/abs/1511.05514)
6. Frans Schalekamp, András Sebő, Vera Traub, and Anke van Zuylen, Layers and matroids for the traveling salesman's paths, Operations Research Letters 46:60-63, 2018. DOI: 10.1016/j.orl.2017.11.002, https://doi.org/10.1016/j.orl.2017.11.002 (preprint arXiv:1703.07170, https://arxiv.org/abs/1703.07170)
7. Vera Traub and Jens Vygen, Approaching 3/2 for the s-t-path TSP, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1854-1864. DOI: 10.1137/1.9781611975031.121, https://doi.org/10.1137/1.9781611975031.121 (preprint arXiv:1707.03992, https://arxiv.org/abs/1707.03992)
8. Rico Zenklusen, A 1.5-Approximation for Path TSP, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 1539-1549. DOI: 10.1137/1.9781611975482.93, https://doi.org/10.1137/1.9781611975482.93 (preprint arXiv:1805.04131, https://arxiv.org/abs/1805.04131)
9. Vera Traub and Jens Vygen, An improved upper bound on the integrality ratio for the s-t-path TSP, Operations Research Letters 47(3):225-228, 2019. DOI: 10.1016/j.orl.2019.02.005, https://doi.org/10.1016/j.orl.2019.02.005 (preprint arXiv:1808.10734, https://arxiv.org/abs/1808.10734)
10. Xianghui Zhong, Slightly improved upper bound on the integrality ratio for the s-t Path TSP, Operations Research Letters 48(5):627-629, 2020. DOI: 10.1016/j.orl.2020.07.015, https://doi.org/10.1016/j.orl.2020.07.015 (preprint arXiv:2004.07217, https://arxiv.org/abs/2004.07217)
11. Vera Traub, Jens Vygen, and Rico Zenklusen, Reducing Path TSP to TSP, SIAM Journal on Computing 51(3), 2022 (published online October 2021; conference version: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pp. 14-27). DOI: 10.1137/20M135594X, https://doi.org/10.1137/20M135594X (preprint arXiv:1907.10376, https://arxiv.org/abs/1907.10376)
12. Anna Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Approximation Algorithm for Metric TSP, 2020. arXiv:2007.01409, https://arxiv.org/abs/2007.01409
13. Anna Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, 2021. arXiv:2105.10043, https://arxiv.org/abs/2105.10043
14. Vera Traub and Jens Vygen, Beating the Integrality Ratio for s-t-Tours in Graphs, SIAM Journal on Computing 52(6), 2023 (conference version: FOCS 2018, pp. 766-777). DOI: 10.1137/18M1227135, https://doi.org/10.1137/18M1227135 (preprint arXiv:1804.03112, https://arxiv.org/abs/1804.03112)
15. Vera Traub, Improving on Best-of-Many-Christofides for T-tours, Operations Research Letters 48(6):798-804, 2020. DOI: 10.1016/j.orl.2020.09.009, https://doi.org/10.1016/j.orl.2020.09.009 (preprint arXiv:2009.09743, https://arxiv.org/abs/2009.09743)
16. Junho Hwang, A 5/4 bound for graphic s-t path TSP on subcubic graphs, 2026. arXiv:2608.11038, https://arxiv.org/abs/2608.11038