The exact integrality ratio of the Held-Karp relaxation for the metric s-t path TSP

The metric s-t path TSP asks for a shortest Hamiltonian path between two prescribed endpoints in a finite metric space. The natural linear-programming (Held-Karp, or subtour) relaxation for this problem is conjectured to have integrality ratio exactly $3/2$: simple instances, already with unit-length graphic metrics (distances given by shortest paths in an unweighted graph), attain $3/2$ asymptotically, while the best proven upper bound stands at $1.5273$ (Zhong, 2020), after $1.5284$ (Traub-Vygen, 2019) and $3/2+1/34$ (Sebő-van Zuylen, 2019). None of the celebrated sub-$3/2$ approximation algorithms for the path TSP — Zenklusen's $3/2$, or the Traub-Vygen-Zenklusen reduction combined with Karlin-Klein-Oveis Gharan's better-than-$3/2$ metric TSP algorithm — is LP-relative, so they leave the ratio open. Distilled from the two open questions stated in Zenklusen's 'A 1.5-Approximation for Path TSP' (SODA 2019), after the companion approximation-factor question was resolved affirmatively in 2021, the surviving problem is to determine the exact integrality ratio: prove that every metric instance satisfies $\mathrm{OPT}\le\frac{3}{2}\,\mathrm{LP}$, or refute the conjecture by exhibiting instances whose ratio exceeds $3/2$ by a fixed margin.

Background

In the metric traveling salesman problem (TSP) one is given a finite metric space $(V,c)$ — pairwise distances on a vertex set satisfying the triangle inequality — and seeks a minimum-cost Hamiltonian cycle. The metric $s$-$t$ path TSP (Path TSP) is the variant in which two distinct endpoints $s,t\in V$ are prescribed and one seeks a minimum-cost Hamiltonian path from $s$ to $t$. Both problems can be restated as finding a minimum-cost connected multi-subset of edges in which every vertex has even degree (TSP), or in which exactly $s$ and $t$ have odd degree (the path version); such a multiset carries an Eulerian walk that can be shortcut, by the triangle inequality, to a Hamiltonian solution.

The Christofides-Serdyukov algorithm — a minimum spanning tree plus a minimum-cost matching on the vertices whose tree degree has the wrong parity — achieves approximation ratio $3/2$ for metric TSP. Wolsey's analysis of it is LP-relative, meaning the output cost is compared to the optimum of the Held-Karp relaxation rather than directly to the optimum tour: the relaxation is the linear program over nonnegative edge vectors $x$ on the complete graph with degree constraints $x(\delta(v))=2$ for every vertex $v$ and subtour constraints $x(\delta(S))\ge 2$ for every nonempty proper vertex set $S$, where $x(\delta(S))$ denotes the total $x$-value on edges crossing the cut $\delta(S)$. Wolsey's argument proves that the integrality ratio of this relaxation — the supremum of the ratio of the optimum tour cost to the LP optimum over all instances — is at most $3/2$ for TSP, where it is conjectured to be $4/3$.

For the $s$-$t$ path TSP the analogous relaxation replaces the degree constraints by $x(\delta(v))=2$ for $v\notin\{s,t\}$ and $x(\delta(v))=1$ for $v\in\{s,t\}$, and weakens the cut constraint to $x(\delta(S))\ge 1$ whenever $S$ separates $s$ from $t$. Hoogeveen's Christofides-type algorithm attains only $5/3$ on this problem, and Wolsey's argument breaks down precisely on the narrow cuts — cuts separating $s$ from $t$ on which the LP solution has value strictly below $2$. An, Kleinberg and Shmoys showed that the narrow cuts of a Held-Karp solution form a chain (any two of the cuts are nested), and a sequence of works exploiting this structure improved the approximation ratio for the metric path TSP: $5/3$ (Hoogeveen, 1991), $1.618$ (An-Kleinberg-Shmoys, 2015), $1.6$ (Sebő, 2013), $1.599$ (Vygen, 2016), $1.566$ (Gottschalk-Vygen, 2018), $3/2+1/34$ (Sebő-van Zuylen, 2019), $3/2+\varepsilon$ for any fixed $\varepsilon>0$ (Traub-Vygen, 2019), and finally $3/2$ (Zenklusen, SODA 2019), whose analysis uses a dynamic program over the polynomially many near-minimum $s$-$t$ cuts instead of the narrow-cut chain. The Sebő-van Zuylen entry is a variation of best-of-many Christofides — an algorithm that samples a spanning tree from a convex decomposition of the LP optimum (a representation of the fractional LP solution as a convex combination of spanning trees) instead of using a single minimum spanning tree — enhanced by lonely-edge deletion: a lonely edge is a tree edge that is the unique tree edge crossing some narrow cut, and deleting lonely edges before the parity correction saves cost because the correction matching often reconnects the resulting pieces anyway (two copies of a deleted edge are added back when it does not).

Crucially, the best approximation algorithms are not LP-relative: Traub and Vygen write that their $3/2+\varepsilon$ algorithm and Zenklusen's $3/2$ algorithm 'do not imply an upper bound on the integrality ratio of the LP', and Zenklusen states explicitly that his approach 'does not imply a new upper bound on the integrality gap of the Held-Karp relaxation for Path TSP, which is believed to be 1.5'. The known upper bounds on the ratio come instead from LP-relative analyses of the weaker best-of-many algorithm with lonely-edge deletion. For the path relaxation the integrality ratio is known to be at least $3/2$, attained asymptotically by simple instances that already arise from unit-length graphic metrics (costs given by shortest paths in an unweighted graph); in that graphic special case the ratio is known to be exactly $3/2$ (Sebő-Vygen, 2014), so the open content concerns general metrics, where the best proven upper bound is $1.5273$ (Zhong, 2020).

The source paper's first open question — whether the approximation factor for Path TSP can be improved below $3/2$ — was resolved affirmatively shortly after: Traub-Vygen-Zenklusen (2020) gave a black-box reduction showing that any $\alpha$-approximation for TSP yields an $(\alpha+\varepsilon)$-approximation for Path TSP, and Karlin-Klein-Oveis Gharan (2021) obtained a randomized $(3/2-\varepsilon)$-approximation for metric TSP with $\varepsilon>10^{-36}$, which by that reduction yields a randomized better-than-$3/2$ algorithm for the TSP path (stated as Theorem 1.2 of their paper). These algorithms, too, are not LP-relative. What survives is the second open question, on which this record focuses: the exact integrality ratio of the Held-Karp relaxation for the metric $s$-$t$ path TSP.

Problem Statement

Determine the exact integrality ratio of the Held-Karp (subtour) relaxation for the metric $s$-$t$ path TSP. For a finite metric space $(V,c)$ with distinct $s,t\in V$, let $\mathrm{OPT}(V,c,s,t)$ be the minimum cost of a Hamiltonian path from $s$ to $t$ (a spanning path visiting every vertex exactly once), and let $\mathrm{LP}(V,c,s,t)$ be the optimum of the linear program

$$\min \sum_{\{u,v\}\in\binom{V}{2}} c(u,v)\,x_{uv}$$ $$x(\delta(v))=2 \quad \forall v\in V\setminus\{s,t\},\qquad x(\delta(v))=1 \quad \forall v\in\{s,t\},$$ $$x(\delta(S))\ge 2 \quad \forall\, \emptyset\neq S\subsetneq V \text{ with } |S\cap\{s,t\}|\in\{0,2\},$$ $$x(\delta(S))\ge 1 \quad \forall\, S\subsetneq V \text{ with } |S\cap\{s,t\}|=1,\qquad x_{uv}\ge 0 \quad \forall \{u,v\}\in\binom{V}{2},$$

where $\binom{V}{2}$ is the set of two-element subsets of $V$ (the variable set), and $x(\delta(W)):=\sum_{u\in W,\, v\in V\setminus W} x_{uv}$ denotes the total $x$-value on the pairs crossing the cut of $W\subseteq V$. The integrality ratio of the relaxation is

$$r \;=\; \sup_{(V,c,s,t)} \frac{\mathrm{OPT}(V,c,s,t)}{\mathrm{LP}(V,c,s,t)},$$

the supremum taken over all finite metric spaces $(V,c)$ and all distinct endpoints $s,t\in V$. Instances with unit-length graphic metrics attain $3/2$ asymptotically, so $r\ge 3/2$, and the conjecture — stated explicitly in the source paper's conclusions and repeated in the intervening literature — is $r=3/2$. The problem is to settle this conjecture: either prove that $\mathrm{OPT}\le\frac{3}{2}\,\mathrm{LP}$ for every finite metric instance (which, combined with the known lower bound, yields $r=3/2$ exactly), or refute it by exhibiting a single instance with $\mathrm{OPT}/\mathrm{LP}>3/2$, or a family of instances whose ratios are bounded below by $\frac{3}{2}+\delta$ for some fixed $\delta>0$ that does not tend to zero across the family.

References

1. 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; arXiv:1805.04131. DOI: 10.1137/1.9781611975482.93. https://arxiv.org/abs/1805.04131
2. Vera Traub, 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; 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):627-629, 2020. DOI: 10.1016/j.orl.2020.07.015; arXiv:2004.07217. https://arxiv.org/abs/2004.07217
4. András Sebő, Anke van Zuylen. The Salesman's Improved Paths through Forests. Journal of the ACM 66(4):1-16, 2019. DOI: 10.1145/3326123; conference version: The Salesman's Improved Paths: A 3/2+1/34 Approximation, FOCS 2016, pp. 118-127, DOI: 10.1109/FOCS.2016.21; arXiv:1604.02486 (under the longer title The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio). https://arxiv.org/abs/1604.02486
5. Vera Traub, Jens Vygen. Approaching 3/2 for the s-t-path TSP. Journal of the ACM 66(2):1-17, 2019. DOI: 10.1145/3309715; conference version: SODA 2018; arXiv:1707.03992. https://arxiv.org/abs/1707.03992
6. Vera Traub, Jens Vygen, Rico Zenklusen. Reducing Path TSP to TSP. SIAM Journal on Computing 51(3):STOC20-24-STOC20-53, 2022; conference version: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pp. 14-27. DOI: 10.1137/20M135594X; arXiv:1907.10376. https://arxiv.org/abs/1907.10376
7. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan. A (Slightly) Improved Approximation Algorithm for Metric TSP. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pp. 32-45. DOI: 10.1145/3406325.3451009; journal version: Operations Research 72(6):2543-2594, 2024, DOI: 10.1287/opre.2022.2338; arXiv:2007.01409. https://arxiv.org/abs/2007.01409
8. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan. A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), Lecture Notes in Computer Science vol. 13904, pp. 261-274. DOI: 10.1007/978-3-031-32726-1_19. https://doi.org/10.1007/978-3-031-32726-1_19
9. Hyung-Chan An, Robert Kleinberg, 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; arXiv:1110.4604. https://arxiv.org/abs/1110.4604
10. 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
11. András Sebő, 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):597-629, 2014. DOI: 10.1007/s00493-014-2960-3. https://doi.org/10.1007/s00493-014-2960-3
12. Corinna Gottschalk, Jens Vygen. Better s-t-tours by Gao trees. Mathematical Programming 172(1-2):191-207, 2018. DOI: 10.1007/s10107-017-1202-z. https://doi.org/10.1007/s10107-017-1202-z
13. András Sebő. Eight-Fifth Approximation for the Path TSP. Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO 2013), Lecture Notes in Computer Science vol. 7801, pp. 362-374. DOI: 10.1007/978-3-642-36694-9_31. https://doi.org/10.1007/978-3-642-36694-9_31
14. Anna Köhne, Vera Traub, Jens Vygen. The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming 183(1-2):379-395, 2020. DOI: 10.1007/s10107-019-01450-8. https://doi.org/10.1007/s10107-019-01450-8
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; arXiv:2009.09743. https://arxiv.org/abs/2009.09743
16. Jens Vygen. Reassembling Trees for the Traveling Salesman. SIAM Journal on Discrete Mathematics 30(2):875-894, 2016. DOI: 10.1137/15M1010531; arXiv:1502.03715. https://arxiv.org/abs/1502.03715