The four-thirds conjecture for the subtour elimination relaxation of the metric traveling salesman problem and the existence of a 4/3-approximation algorithm

Boyd, Sitters, van der Ster, and Stougie (Mathematical Programming 2014, on graphic TSP for cubic and subcubic graphs) pose as their most prominent open question the famous four-thirds conjecture: the integrality gap of the subtour elimination linear-programming relaxation (SER, also called the Held–Karp LP) of the symmetric metric traveling salesman problem is exactly $4/3$, and correspondingly a polynomial-time $4/3$-approximation algorithm for metric TSP should exist. The problem is open: the gap is proven to lie between $4/3$ (asymptotically attained by explicit families, already on graphic instances of subcubic graphs) and $3/2-10^{-36}$ (Karlin–Klein–Oveis Gharan 2021). Several sub-questions raised by the source have since been resolved: the $3/2$ barrier for graphic TSP on general graphs fell to $7/5$ (Sebő–Vygen); graphic TSP on cubic graphs, where the source proved a $4/3$-approximation and a lower bound of $7/6$ on the integrality gap, now admits a $5/4$-approximation (Wigal–Yoo–Yu 2023), so $4/3$ is not tight; and the conjectured APX-hardness of graphic TSP on cubic graphs was proved (Karpinski–Schmied 2015). The remaining open problems are the exact integrality gap of the subtour LP for graphic TSP on general graphs (between $4/3$ and $7/5$) and on cubic graphs (between $7/6$ and $5/4$).

Background

In the symmetric metric traveling salesman problem (TSP), one is given $n$ points with distances $c_{ij}=c_{ji}$ satisfying the triangle inequality, and seeks a shortest closed tour visiting every point exactly once; equivalently, a shortest closed walk visiting all points. The standard linear-programming relaxation is the subtour elimination relaxation (SER), also called the Held–Karp relaxation: with a variable $x_{ij}\ge 0$ on every pair of points, minimize $\sum_{i<j} c_{ij}x_{ij}$ subject to $x(\delta(v))=2$ for every point $v$ (each point has total incident weight 2) and $x(\delta(S))\ge 2$ for every nonempty proper subset $S$ of the points (no cut is crossed with weight less than 2, which enforces connectivity). The integrality gap of SER is the worst-case ratio $\mathrm{OPT}(I)/\mathrm{SER}(I)$ between the optimal tour length and the LP optimum, taken over all instances; it measures how far the LP can be from the truth. The four-thirds conjecture, open since the 1980s, asserts that this gap is exactly $4/3$. The lower bound $4/3$ is asymptotically attained by explicit instance families, including graphic ones (Benoit–Boyd 2008 computed exact gaps for small instances and exhibited families approaching $4/3$). The upper bound $3/2$ follows from Wolsey's analysis of the Christofides–Serdyukov algorithm (spanning tree plus a minimum-weight perfect matching on its odd-degree vertices, shortcut to a tour); this $3/2$ guarantee stood for roughly forty years until Karlin–Klein–Oveis Gharan (2021) proved the gap is at most $3/2-\epsilon$ for some $\epsilon>10^{-36}$ via max-entropy rounding. Jin–Klein–Williamson (2023) showed the max-entropy algorithm itself has ratio at least $1.375$ even on graphic instances, so it cannot be the route to $4/3$. Because SER is the relaxation that state-of-the-art exact TSP solvers actually optimize, the conjecture is the central open question about the quality of the industry-standard TSP bound; its constructive form — a polynomial-time algorithm producing a tour of cost at most $4/3\cdot\mathrm{SER}(I)$ — would be the first qualitative improvement of metric TSP approximation in over four decades.

A prominent family of conjectured worst-case instances is graphic: given an unweighted graph $G$ (all edges of length 1), the TSP distances are the shortest-path distances of $G$, and the graphic TSP asks for a shortest closed walk in $G$ visiting all vertices. A graph is cubic if every vertex has degree exactly 3 and subcubic if every degree is at most 3; these are among the simplest classes on which the problem stays NP-hard, and the known families with integrality gap approaching $4/3$ live on subcubic graphs. Motivated by this, Boyd, Sitters, van der Ster, and Stougie (2014) proved that graphic TSP on simple cubic graphs admits a $4/3$-approximation — a tour of length at most $4n/3-2$ on bridgeless cubic graphs ($n$ vertices), extended to cubic graphs with bridges — and constructed cubic graph families whose subtour-LP integrality gap is at least $7/6$ (tours of length at least $11n/9-8/9$). On graphic instances the SER value is always at least $n$ (each pair distance is at least 1 and the degree constraints force total variable weight exactly $n$), so tour-length bounds translate directly into integrality-gap bounds: at the source's publication the integrality gap on cubic graphs was confined to $[7/6,4/3]$. The source posed the four-thirds conjecture itself as its headline open question, together with derived questions: the exact gap for graphic TSP, whether graphic TSP on cubic graphs is APX-hard (APX-hardness rules out a polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$), and whether $4/3$ is tight for cubic and subcubic graphs.

Problem Statement

Let $I$ be a finite symmetric metric TSP instance: $n$ points with rational distances $c_{ij}=c_{ji}$, $c_{ii}=0$, $c_{ij}>0$ for $i\ne j$, satisfying the triangle inequality. Let $\mathrm{SER}(I)$ denote the optimum of the subtour elimination relaxation (Held–Karp LP) of $I$ — minimize $\sum_{i<j}c_{ij}x_{ij}$ subject to $x(\delta(v))=2$ for every point $v$, $x(\delta(S))\ge 2$ for every nonempty proper subset $S$ of points, and $x\ge 0$ — and let $\mathrm{OPT}(I)$ be the length of a shortest tour. Let $\gamma=\sup_{I}\mathrm{OPT}(I)/\mathrm{SER}(I)$ over all finite symmetric metric instances. Determine $\gamma$: prove or refute the four-thirds conjecture $\gamma=4/3$. In constructive form: does there exist a polynomial-time algorithm that, for every such instance $I$, outputs a tour of length at most $\frac{4}{3}\,\mathrm{SER}(I)$? Currently only $4/3\le\gamma\le 3/2-10^{-36}$ is proven, so both an upper-bound proof of $4/3$ and an explicit instance family with $\mathrm{OPT}/\mathrm{SER}>4/3$ would constitute decisive answers; the constructive and gap questions are linked but not equivalent, since a nonconstructive proof of $\gamma\le 4/3$ would not by itself yield the algorithm.

Boyd et al. (2014) pose this as their most prominent open question; as derived restrictions of the same gap question to nested instance classes, they also ask for the exact integrality gap of the subtour LP on graphic instances — where it is currently confined to $[4/3,7/5]$ on arbitrary graphs — and on instances arising from cubic graphs, where the bounds $7/6\le\mathrm{gap}\le 4/3$ proved there have been narrowed to $7/6\le\mathrm{gap}\le 5/4$ on 2-connected cubic graphs by Wigal–Yoo–Yu (2023). These graphic and cubic sub-questions are illustrations of the same question: the conjectured worst case for the general metric question is already believed to be attained on graphic subcubic instances, so any complete resolution of the general problem above must in particular be consistent with (and is expected to illuminate) the graphic and cubic cases.

References

1. Sylvia Boyd, René Sitters, Suzanne van der Ster, Leen Stougie: The traveling salesman problem on cubic and subcubic graphs. Mathematical Programming 144 (2014) 227–245. DOI 10.1007/s10107-012-0620-1. https://doi.org/10.1007/s10107-012-0620-1
2. Nishita Aggarwal, Naveen Garg, Swati Gupta: A 4/3-approximation for TSP on cubic 3-edge-connected graphs. arXiv:1101.5586 (2011). https://arxiv.org/abs/1101.5586
3. Geneviève Benoit, Sylvia Boyd: Finding the exact integrality gap for small traveling salesman problems. Mathematics of Operations Research 33 (2008) 921–931. DOI 10.1287/moor.1080.0337. https://doi.org/10.1287/moor.1080.0337
4. Anna Karlin, Nathan Klein, Shayan Oveis Gharan: A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. arXiv:2105.10043 (2021). https://arxiv.org/abs/2105.10043
5. Billy Jin, Nathan Klein, David P. Williamson: A Lower Bound for the Max Entropy Algorithm for TSP. arXiv:2311.01950 (2023). https://arxiv.org/abs/2311.01950
6. Shayan Oveis Gharan, Amin Saberi, Mohit Singh: A Randomized Rounding Approach to the Traveling Salesman Problem. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 550–559. DOI 10.1109/focs.2011.80. https://doi.org/10.1109/focs.2011.80
7. Tobias Mömke, Ola Svensson: Removing and Adding Edges for the Traveling Salesman Problem. Journal of the ACM 63 (2016), no. 1, article 2, pp. 2:1–2:28. DOI 10.1145/2739008. https://doi.org/10.1145/2739008
8. Marcin Mucha: $\frac{13}{9}$-Approximation for Graphic TSP. Theory of Computing Systems 55 (2014) 640–657. DOI 10.1007/s00224-012-9439-7. https://doi.org/10.1007/s00224-012-9439-7
9. 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 (2014) 597–629. DOI 10.1007/s00493-014-2960-3; arXiv:1201.1870. https://doi.org/10.1007/s00493-014-2960-3
10. Ali Çivril: 4/3-Approximation of Graphic TSP. arXiv:2305.05411 (2023). https://arxiv.org/abs/2305.05411
11. Marek Karpinski, Michael Lampis, Richard Schmied: New inapproximability bounds for TSP. Journal of Computer and System Sciences 81 (2015) 1665–1677. DOI 10.1016/j.jcss.2015.06.003; arXiv:1303.6437. https://arxiv.org/abs/1303.6437
12. Marek Karpinski, Richard Schmied: Approximation hardness of graphic TSP on cubic graphs. RAIRO – Operations Research 49 (2015) 651–668. DOI 10.1051/ro/2014062; arXiv:1304.6800. https://arxiv.org/abs/1304.6800
13. José R. Correa, Omar Larré, José A. Soto: TSP Tours in Cubic Graphs: Beyond 4/3. SIAM Journal on Discrete Mathematics 29 (2015) 915–939. DOI 10.1137/140972925. https://doi.org/10.1137/140972925
14. Anke van Zuylen: Improved approximations for cubic bipartite and cubic TSP. Mathematical Programming 172 (2017) 399–413. DOI 10.1007/s10107-017-1211-y; arXiv:1507.07121. https://arxiv.org/abs/1507.07121
15. Jeremy Karp, R. Ravi: A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs. arXiv:1311.3640 (2013). https://arxiv.org/abs/1311.3640
16. Barbora Duník, Robert Lukoťka: Cubic TSP: A 1.3-Approximation. SIAM Journal on Discrete Mathematics 32 (2018) 2094–2114. DOI 10.1137/15M1032247. https://doi.org/10.1137/15M1032247
17. Zdeněk Dvořák, Daniel Král', Bojan Mohar: Graphic TSP in cubic graphs. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017); arXiv:1608.07568. https://arxiv.org/abs/1608.07568
18. Michael C. Wigal, Youngho Yoo, Xingxing Yu: Approximating TSP walks in subcubic graphs. Journal of Combinatorial Theory, Series B 158 (2023) 70–104. DOI 10.1016/j.jctb.2022.09.002; arXiv:2112.06278. https://arxiv.org/abs/2112.06278
19. Robert Lukoťka, Ján Mazák: Simple cubic graphs with no short traveling salesman tour. arXiv:1712.10167 (2017). https://arxiv.org/abs/1712.10167
20. Junho Hwang: A 5/4 Bound for Graphic $s$–$t$ Path TSP on Subcubic Graphs. arXiv:2608.11038 (2026). https://arxiv.org/abs/2608.11038
21. Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, Dániel Marx: From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity. arXiv:2502.18541 (2025). https://arxiv.org/abs/2502.18541