The 4/3 conjecture for the integrality gap of the subtour elimination relaxation of the metric traveling salesman problem

The source is the set of open problems closing Boyd, Sitters, van der Ster and Stougie's paper on the traveling salesman problem (TSP) on cubic and subcubic graphs (Mathematical Programming 2014; arXiv:1107.1052): whether simple cubic graphs admit a polynomial-time algorithm for graphic TSP with approximation ratio strictly below 4/3, whether graphic TSP on cubic graphs is APX-hard (i.e., admits no polynomial-time approximation scheme unless P = NP), whether any algorithm for general metric TSP can beat 3/2, whether better lower bounds for graph-TSP optima can be found, and — stated as the main research challenge — Conjecture 1: the integrality gap of the subtour elimination relaxation (SER, the subtour LP) for metric TSP equals 4/3. The cubic-graph sub-questions were resolved affirmatively (algorithms with ratios 4/3−ε, then 9/7, then 5/4 on simple cubic graphs; APX-hardness proved with constant 1153/1152), and the 3/2 barrier for metric TSP fell to a randomized 3/2−ε algorithm. The surviving open core is the 4/3 conjecture itself: determine whether the worst-case ratio OPT/SER over all finite metric instances equals 4/3. Currently the gap is known to lie between 4/3 and 3/2−10^{-36}, with the conjecture confirmed only on restricted classes such as subcubic graphic instances, half-integral cycle-cut instances, instances with at most n+6 nonzeros in an optimal LP solution, and all instances with up to 15 vertices.

Background

An instance of the symmetric traveling salesman problem (TSP) is a complete graph on $n$ vertices whose edge costs satisfy the triangle inequality (a metric); the task is to find a minimum-cost Hamiltonian cycle, called a tour. Metric TSP is NP-hard; the classical Christofides algorithm achieves approximation ratio $3/2$. An important special case is the graphic TSP (graph-TSP): the metric is the shortest-path metric of an unweighted graph $G$ (its metric completion), and finding a tour is equivalent to finding a spanning closed walk of $G$, i.e. a minimum-size spanning Eulerian multisubgraph of $G$.

The central relaxation is the subtour elimination relaxation (SER), also called the subtour LP or the Dantzig–Fulkerson–Johnson subtour formulation; its optimum is known as the Held–Karp lower bound. In edge variables $x\ge 0$ on the complete graph it reads $\min \sum_e c_e x_e \quad \text{s.t.} \quad x(\delta(v))=2 \ \ \forall v, \qquad x(\delta(S))\ge 2 \ \ \forall\, \emptyset\ne S\ne V,$ where $\delta(S)$ is the set of edges crossing the cut of $S$ and $x(F)=\sum_{e\in F}x_e$. The integrality gap $\alpha(\mathrm{TSP})$ is the worst case, over all finite metric instances $I$, of the ratio $\mathrm{OPT}(I)/\mathrm{SER}(I)$ between the optimal tour cost and this LP bound. A constructive proof that $\alpha\le\beta$ yields a $\beta$-approximation algorithm, since $\mathrm{SER}\le\mathrm{OPT}$.

Two classical benchmarks anchor the gap. The upper bound $\alpha\le 3/2$ follows from Wolsey's 1980 analysis showing the Christofides tour costs at most $3/2$ times the SER bound; it stood for about forty years. The lower bound $\alpha\ge 4/3$ is attained asymptotically by simple subcubic graphic instances: two vertices joined by three equal paths of length $k$ (theta graphs), for which $\mathrm{OPT}/\mathrm{SER}\to 4/3$ as $k\to\infty$. The 4/3 conjecture, dating to the early 1980s, asserts that the gap is exactly $4/3$.

Cubic and subcubic graphs (all vertex degrees equal to 3, respectively at most 3) have served as the main laboratory for the conjecture, and are the setting of the source paper. A graph is bridgeless if no edge is a cut, and 2-connected if it remains connected after deleting any vertex; by Petersen's classical theorem every bridgeless cubic graph decomposes into a cycle cover (a spanning union of vertex-disjoint cycles) plus a complementary perfect matching. Boyd, Sitters, van der Ster and Stougie used such structure to prove that every cubic graph has a graph-TSP tour of length at most $4n/3-2$, a $4/3$-approximation since any graphic tour visits all $n$ vertices and the SER value is at least $n$. Simultaneously, Mömke and Svensson's matching-based framework gave a $1.461$-approximation for graphic TSP on general graphs and the tight bound $4n/3-2/3$ for subcubic bridgeless graphs, so the gap equals exactly $4/3$ on that class. Later work improved the graphic-TSP ratio to $13/9$ and then $7/5$, which remains the best published ratio for general graphic instances, so for graphic metrics the gap lies between $4/3$ and $7/5$ in the published literature. On simple cubic graphs the ratio was subsequently driven to $9/7$ and then $5/4$ (essentially tight in terms of $n$), and the subtour-LP gap there is known to be strictly below $4/3$ yet at least $7/6$. Exact computations verify the conjecture on all metric instances up to $15$ vertices, and the worst case is believed to occur already at half-integral LP solutions, i.e. solutions whose edge values all lie in $\{0,\tfrac12,1\}$.

Problem Statement

Let $\alpha(\mathrm{TSP})=\sup_I \mathrm{OPT}(I)/\mathrm{SER}(I)$, where the supremum is over all finite instances $I$ of the symmetric metric TSP, $\mathrm{OPT}(I)$ is the minimum tour cost, and $\mathrm{SER}(I)$ is the optimal value of the subtour elimination relaxation (the subtour LP 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$, over the complete graph with the instance's metric costs; also called the Held–Karp bound). It is known that $\alpha(\mathrm{TSP})\ge 4/3$, with the bound attained asymptotically by subcubic graphic instances. Prove or disprove the 4/3 conjecture (Conjecture 1 of the source paper, dating to the early 1980s):

$\alpha(\mathrm{TSP})=\frac{4}{3}.$

Concretely: either prove that every metric TSP instance admits a tour of cost at most $\frac{4}{3}\cdot \mathrm{SER}(I)$ — such an upper bound settles the conjecture given the known lower bound — or refute the conjecture by exhibiting a metric instance, or a family of instances, with $\mathrm{OPT}(I)>\frac{4}{3}\cdot \mathrm{SER}(I)$. Graphic instances (including subcubic ones, where the gap is known to be exactly 4/3) form a strict subclass of metric instances, so resolving the conjecture on any graph-derived subclass does not by itself resolve the general question, which concerns all finite symmetric metric spaces.

References

1. Sylvia Boyd, René Sitters, Suzanne van der Ster, Leen Stougie, 'The traveling salesman problem on cubic and subcubic graphs', Mathematical Programming (2014), DOI 10.1007/s10107-012-0620-1; arXiv:1107.1052, https://arxiv.org/abs/1107.1052
2. Laurence A. Wolsey, 'Heuristic analysis, linear programming and branch and bound', Mathematical Programming Studies (1980), DOI 10.1007/bfb0120913, https://doi.org/10.1007/bfb0120913
3. Tobias Mömke, Ola Svensson, 'Approximating Graphic TSP by Matchings', FOCS 2011, DOI 10.1109/FOCS.2011.56; arXiv:1104.3090, https://arxiv.org/abs/1104.3090
4. Marcin Mucha, '13/9-approximation for Graphic TSP', Theory of Computing Systems (2014), DOI 10.1007/S00224-012-9439-7; arXiv:1108.1130, https://arxiv.org/abs/1108.1130
5. 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 (2014), DOI 10.1007/S00493-014-2960-3; arXiv:1201.1870, https://arxiv.org/abs/1201.1870
6. José R. Correa, Omar Larré, José A. Soto, 'TSP Tours in Cubic Graphs: Beyond 4/3', SIAM Journal on Discrete Mathematics (2015), DOI 10.1137/140972925; arXiv:1310.1896, https://arxiv.org/abs/1310.1896
7. Marek Karpinski, Richard Schmied, 'Approximation hardness of graphic TSP on cubic graphs', RAIRO – Operations Research (2015), DOI 10.1051/ro/2014062; arXiv:1304.6800, https://arxiv.org/abs/1304.6800
8. Jeremy Karp, R. Ravi, 'A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs', APPROX/RANDOM 2014, DOI 10.4230/LIPIcs.APPROX-RANDOM.2014.284, https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.284; arXiv:1311.3640, https://arxiv.org/abs/1311.3640
9. Barbora Candráková, Robert Lukoťka, 'Cubic TSP - a 1.3-approximation', arXiv:1506.06369 (2015), https://arxiv.org/abs/1506.06369
10. Anke van Zuylen, 'Improved approximations for cubic bipartite and cubic TSP', Mathematical Programming (2018), DOI 10.1007/S10107-017-1211-Y; arXiv:1507.07121, https://arxiv.org/abs/1507.07121
11. Zdeněk Dvořák, Daniel Král, Bojan Mohar, 'Graphic TSP in Cubic Graphs', STACS 2017, DOI 10.4230/LIPIcs.STACS.2017.27, https://doi.org/10.4230/LIPIcs.STACS.2017.27; arXiv:1608.07568, https://arxiv.org/abs/1608.07568
12. Robert Lukoťka, Ján Mazák, 'Simple cubic graphs with no short traveling salesman tour', Discrete Applied Mathematics (2018), DOI 10.1016/j.dam.2018.02.023; arXiv:1712.10167, https://arxiv.org/abs/1712.10167
13. Arash Haddadan, Alantha Newman, R. Ravi, 'Shorter tours and longer detours: uniform covers and a bit beyond', Mathematical Programming (2019), DOI 10.1007/s10107-019-01426-8; arXiv:1707.05387, https://arxiv.org/abs/1707.05387
14. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Approximation Algorithm for Metric TSP', STOC 2021, DOI 10.1145/3406325.3451009; Operations Research (2024), DOI 10.1287/opre.2022.2338; arXiv:2007.01409, https://arxiv.org/abs/2007.01409
15. Anna Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP', FOCS 2022, DOI 10.1109/FOCS54457.2022.00084; arXiv:2105.10043, https://arxiv.org/abs/2105.10043
16. Michael C. Wigal, Youngho Yoo, Xingxing Yu, 'Approximating TSP walks in subcubic graphs', Journal of Combinatorial Theory, Series B (2023), DOI 10.1016/j.jctb.2022.09.002; arXiv:2112.06278, https://arxiv.org/abs/2112.06278
17. Billy Jin, Nathan Klein, David P. Williamson, 'A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP', IPCO 2023; Mathematical Programming (2025), DOI 10.1007/S10107-025-02193-5; arXiv:2211.04639, https://arxiv.org/abs/2211.04639
18. Geneviève Benoit, Sylvia Boyd, 'Finding the Exact Integrality Gap for Small Traveling Salesman Problems', Mathematics of Operations Research (2008), DOI 10.1287/moor.1080.0337, https://doi.org/10.1287/moor.1080.0337
19. Tullio Villa, Eleonora Vercesi, Janos Barta, Monaldo Mastrolilli, 'The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components', arXiv:2507.07003 (2025), https://arxiv.org/abs/2507.07003
20. William Cook, Stefan Hougardy, Moritz Petrich, 'Extending Exact Integrality Gap Computations for the Metric TSP', arXiv:2603.12995 (2026), https://arxiv.org/abs/2603.12995
21. Billy Jin, Nathan Klein, David P. Williamson, 'Maximum Entropy is a 10/7-Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances', Operations Research Letters (2026), DOI 10.1016/j.orl.2026.107493; arXiv:2607.01536, https://arxiv.org/abs/2607.01536
22. 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
23. Ali Çivril, '4/3-Approximation of Graphic TSP', arXiv:2305.05411 (2023, v9 2026), https://arxiv.org/abs/2305.05411 — unrefereed preprint; it does not alter the published bounds stated in the Background.