The 4/3-Conjecture for the Integrality Gap of the Subtour (Held–Karp) Relaxation of the Metric Traveling Salesman Problem

The subtour relaxation (subtour LP, or Held–Karp relaxation) is the standard linear programming relaxation of the symmetric traveling salesman problem, built from degree constraints and subtour-elimination constraints. Its integrality gap for metric instances — the worst-case ratio of the length of an optimal tour to the LP optimum — is known to be at least $4/3$, and the long-standing four-thirds conjecture asserts that it is exactly $4/3$. The best proven upper bound is still essentially $3/2$, improved only to $3/2-\epsilon$ for a tiny fixed $\epsilon>0$. Cook, Hougardy, and Petrich (arXiv:2603.12995) pushed exact computational verification to all instances on $n\le15$ vertices (maximum gap $11/9$, attained at the extreme points conjectured by Benoit and Boyd) and to all half-integral vertices for $n\le17$ (maximum $53/43$), while correcting earlier published extreme-point catalogs. This record asks for a resolution of the conjecture itself: prove $\mathrm{OPT}\le\frac{4}{3}\,\mathrm{LP}$ for every metric instance, or refute it with a metric instance, or family, whose ratio provably exceeds $4/3$.

Background

The symmetric traveling salesman problem (TSP) asks for a shortest closed tour visiting each of $n$ vertices exactly once, given pairwise edge costs. In the metric TSP the costs are symmetric and satisfy the triangle inequality. The standard linear programming relaxation — the subtour relaxation, also called the subtour LP or Held–Karp relaxation — minimizes $\sum_e c_e x_e$ subject to the degree constraints $x(\delta(v))=2$ for every vertex $v$ (each vertex is entered and left exactly once; $\delta(v)$ is the set of edges incident to $v$ and $x(\delta(v))$ is the sum of the corresponding variables) and the subtour-elimination constraints $x(\delta(S))\ge 2$ for every nonempty proper vertex subset $S$ (a tour must cross every cut at least twice), with $x\ge 0$. Its optimum is a polynomial-time-computable lower bound on the length of an optimal tour, since the exponentially many subtour-elimination constraints can be separated by minimum-cut computations.

The integrality gap of this relaxation is the worst-case ratio $\mathrm{OPT}/\mathrm{LP}$ between the length of an optimal tour and the LP optimum, taken over all metric instances. Explicit metric constructions show the gap is at least $4/3$, so the bound $4/3$, if achievable, is tight. The four-thirds conjecture (also called the 4/3-conjecture) asserts that the gap is exactly $4/3$, i.e. that $\mathrm{OPT}\le\frac{4}{3}\,\mathrm{LP}$ for every metric instance. The conjecture dates back to the early 1990s — D. P. Williamson's 1990 MIT thesis on the Held–Karp heuristic is an early source, and Goemans (1995) surveys the early comparisons of valid inequalities — and is one of the most prominent open problems in combinatorial optimization. The best proven upper bound is still essentially $3/2$, from the classical analysis of Christofides' spanning-tree-plus-matching algorithm; Karlin, Klein, and Oveis Gharan improved it to $3/2-\epsilon$ for a tiny fixed $\epsilon>0$ (about $10^{-36}$ in their randomized analysis, with a smaller explicit improvement in the deterministic version).

Because the LP optimum is attained at an extreme point (vertex) of the subtour polytope $S^n$ — the set of feasible points of the relaxation on $n$ vertices — the worst-case ratio for instances on $n$ vertices can be computed exactly by enumerating these vertices: Benoit and Boyd (2008) showed that for a vertex $x$ its worst-case gap $\mathrm{gap}^+(x)=\max_c \mathrm{OPT}(c)/(c\cdot x)$ over metric cost functions $c$ is the reciprocal of the optimum of a single linear program minimizing $c\cdot x$ over the metric cone (triangle inequalities, nonnegative costs) subject to every tour having length at least $1$; the maximum of $\mathrm{gap}^+(x)$ over all non-isomorphic vertices of $S^n$ equals the exact integrality gap for $n$ vertices. This reduces finite verification of the conjecture to vertex enumeration — but the number of non-isomorphic vertices grows explosively: about $3.2\times10^8$ at $n=15$ in the general case, and $4.2\times10^7$ half-integral vertices at $n=17$ (half-integral vertices are those whose edge values all lie in $\{0,\frac{1}{2},1\}$, a structured subclass tied to cycle covers that plays a central role in TSP approximation).

Computationally, Benoit and Boyd (2008) verified the conjecture for all instances up to $n=10$ and conjectured which extreme points attain the maximum gap in general; Boyd and Elliott-Magwood (2010) extended the enumeration to $n=12$ (general) and $n=14$ (half-integral), and Boyd's 2011 web page published the vertex lists for $6\le n\le12$. Cook, Hougardy, and Petrich (2026) re-ran and extended this program with modern tools (nauty for support-graph generation, the Parma Polyhedra Library for vertex enumeration, cutting-plane gap LPs with exact rational verification): they found the previously published vertex lists were incomplete (1 vertex missing at $n=11$, 22 at $n=12$, and 5 and 18 half-integral vertices at $n=13$ and $n=14$), enumerated all vertices for $n\le15$ in the general case (maximum gap $11/9\approx1.2222$ at $n=15$) and all half-integral vertices for $n\le17$ (maxima $27/22\approx1.2273$ at $n=16$ and $53/43\approx1.2326$ at $n=17$), and published the full lists on the bonndata repository. In every case the maximum is still uniquely attained at the extreme points conjectured by Benoit and Boyd, so the observed maxima trace the conjectured worst-case family towards $4/3$ without exceeding it.

The conjecture is proven only for special classes: cubic and subcubic graph metrics (Boyd, Sitters, van der Ster, and Stougie 2014), half-integral cycle-cut instances — instances whose LP optimum is half-integral and whose support admits a certain laminar cut structure (Jin, Klein, and Williamson 2025) — and instances whose optimal LP solution has at most $n+6$ nonzero components (Villa, Vercesi, Barta, and Mastrolilli 2025). On the algorithmic side, the max-entropy rounding algorithm — which converts the fractional LP solution into a tour by sampling a spanning tree from the maximum-entropy distribution over the spanning trees contained in the LP support and adding a minimum matching on the resulting odd-degree vertices — powers the only better-than-$3/2$ approximation, yet it has a proven lower bound of $11/8$ on its approximation ratio and is a $10/7$-approximation on half-integral cycle-cut instances (both Jin, Klein, and Williamson 2026), so no current rounding analysis reaches $4/3$ on general instances.

Problem Statement

Prove or refute the 4/3-conjecture for the symmetric metric traveling salesman problem.

For a finite vertex set $V$ and a symmetric cost function $c$ on the edges of the complete graph on $V$ satisfying the triangle inequality, let $\mathrm{OPT}(V,c)$ be the minimum length of a Hamiltonian cycle (tour) and $\mathrm{LP}(V,c)$ the optimum of the subtour relaxation

$$\min \sum_{e} c_e x_e \quad\text{s.t.}\quad x(\delta(v))=2\ \ \forall v\in V,\qquad x(\delta(S))\ge 2\ \ \forall\,\emptyset\neq S\subsetneq V,\qquad x\ge 0.$$

The conjecture asserts that $\mathrm{OPT}(V,c)\le\frac{4}{3}\,\mathrm{LP}(V,c)$ for every finite vertex set $V$ and every such cost function $c$; since constructions are known for which the ratio is at least $\frac{4}{3}$, a proof pins the integrality gap at exactly $\frac{4}{3}$.

A resolution of the conjecture is one of the following.

(a) Prove the inequality for all metric instances and all numbers of vertices. A bound weaker than $\frac{4}{3}$, or a proof restricted to a subclass (half-integral solutions, bounded support size, graph metrics, cycle-cut structure, etc.), establishes only a partial result.

(b) Refute the conjecture: exhibit one concrete metric instance whose exactly certified ratio $\mathrm{OPT}/\mathrm{LP}$ is strictly greater than $\frac{4}{3}$, or an explicit infinite family of metric instances whose ratios are provably bounded below by $\frac{4}{3}+\delta$ for some fixed $\delta>0$.

Extending the exhaustive verification to larger $n$ is a separate computational question and does not by itself resolve the conjecture.

References

1. William Cook, Stefan Hougardy, Moritz Petrich. Extending Exact Integrality Gap Computations for the Metric TSP. arXiv:2603.12995 (v4, 2026). https://arxiv.org/abs/2603.12995
2. William Cook, Stefan Hougardy, Moritz Petrich. Vertices of the Subtour Polytope (extreme-point lists, bonndata repository, 2026). doi:10.60507/FK2/JK95PC, https://bonndata.uni-bonn.de/catalog/datasets/10.60507/FK2/JK95PC/
3. Geneviève Benoit, Sylvia Boyd. Finding the exact integrality gap for small traveling salesman problems. Mathematics of Operations Research 33(4):921–931, 2008. doi:10.1287/moor.1080.0337, https://doi.org/10.1287/moor.1080.0337
4. Sylvia Boyd, Paul Elliott-Magwood. Structure of the extreme points of the subtour elimination polytope of the STSP. RIMS Kôkyûroku Bessatsu B23:33–47, 2010. Zbl 1223.90050, https://www.site.uottawa.ca/~sylvia/publications/boydelliottmagwoodsubtourptsKyoto2010.pdf
5. Sylvia Boyd. Vertices of the subtour elimination polytope (web resource listing all non-isomorphic vertices for 6 ≤ n ≤ 12), 2011. https://www.site.uottawa.ca/~sylvia/subtourvertices/index.htm
6. Sylvia Boyd, René Sitters, Suzanne van der Ster, Leen Stougie. The traveling salesman problem on cubic and subcubic graphs. Mathematical Programming 144:227–245, 2014. doi:10.1007/s10107-012-0620-1, https://doi.org/10.1007/s10107-012-0620-1
7. Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP. Mathematical Programming 69:335–349, 1995. doi:10.1007/BF01585563, https://doi.org/10.1007/BF01585563
8. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan. A deterministic better-than-3/2 approximation algorithm for metric TSP. Integer Programming and Combinatorial Optimization (IPCO 2023), LNCS, 261–274, 2023. doi:10.1007/978-3-031-32726-1_19, https://doi.org/10.1007/978-3-031-32726-1_19
9. Billy Jin, Nathan Klein, David P. Williamson. A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP. Mathematical Programming 210:511–538, 2025. doi:10.1007/s10107-025-02193-5, https://doi.org/10.1007/s10107-025-02193-5
10. Billy Jin, Nathan Klein, David P. Williamson. A lower bound for the max entropy algorithm for TSP. Mathematical Programming 216:425–447, 2026. doi:10.1007/s10107-025-02289-y, https://doi.org/10.1007/s10107-025-02289-y
11. Billy Jin, Nathan Klein, David P. Williamson. Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances. arXiv:2607.01536 (2026). https://arxiv.org/abs/2607.01536
12. 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 (v2, 2025). https://arxiv.org/abs/2507.07003
13. Toshiaki Yamanaka. TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima. arXiv:2511.11215 (v2, 2025). https://arxiv.org/abs/2511.11215
14. Xianghui Zhong. Lower bounds on the integrality ratio of the subtour LP for the traveling salesman problem. Discrete Applied Mathematics 365:109–129, 2025. doi:10.1016/j.dam.2024.12.029, https://doi.org/10.1016/j.dam.2024.12.029
15. Eleonora Vercesi, Stefano Gualandi, Monaldo Mastrolilli, Luca Maria Gambardella. On the generation of metric TSP instances with a large integrality gap by branch-and-cut. arXiv:2109.02454 (v3, 2023). https://arxiv.org/abs/2109.02454