Schalekamp–Williamson–van Zuylen conjecture: is the integrality gap of the subtour LP attained on half-integral vertices?

The source paper (Karlin–Klein–Oveis Gharan, arXiv:1908.00227, 2019) proved a randomized 1.49993-approximation for metric TSP instances whose subtour LP optimum is half-integral, with its integrality-gap consequence conditional on the Schalekamp–Williamson–van Zuylen (SWvZ) conjecture that the worst-case integrality gap of the subtour LP is attained on half-integral vertices. The source's subsidiary goals have since been met by other means: a randomized $3/2-\epsilon$ approximation for all metric instances ($\epsilon>10^{-36}$) has existed since 2020, the half-integral guarantee now stands at 1.49776, and the half-integral 2-edge-connected multisubgraph case admits a $4/3$-approximation. The SWvZ conjecture itself remains open: the half-integral supremum lies in $[4/3,1.49776]$, the general gap in $[4/3,3/2-\epsilon]$, extreme-point enumeration up to $n=15$ (17 for half-integral vertices) supports it, and no metric instance with integrality ratio above $4/3$ — which any refutation would require — has ever been exhibited.

Background

The symmetric traveling salesperson problem (TSP) on a metric asks for a minimum-cost Hamiltonian cycle in a complete graph whose edge costs obey the triangle inequality. Its standard linear programming relaxation is the subtour LP (also called the subtour elimination LP or Held–Karp relaxation): minimize the cost of an edge vector $x$ subject to $x(\delta(\{v\}))=2$ for every vertex $v$ (each vertex has total incident value 2), $x(\delta(S))\ge 2$ for every vertex subset $S$ with $2\le |S|\le n-2$ (no subtour may live inside a strict subset of the vertices), and $x_e\ge 0$, where $\delta(S)$ denotes the set of edges with exactly one endpoint in $S$. The integrality gap of this relaxation is the supremum, over all metric instances $I$, of $\mathrm{OPT}(I)/\mathrm{LP}(I)$, the ratio of the optimal tour cost to the optimal LP value. The classical analysis of the Christofides–Serdyukov algorithm (take a minimum spanning tree and add a minimum-cost perfect matching on its odd-degree vertices) shows the gap is at most $3/2$, while explicit constructions — the envelope-graph instances for graph metrics and the weighted $k$-donut instances (two hand-built families of metric costs whose subtour LP optima are half-integral and whose optimal tours cost asymptotically $4/3$ times the LP value) — show it is at least $4/3$. Whether the gap is exactly $4/3$ is the four-thirds conjecture, a long-standing open problem.

A feasible point of the subtour LP is half-integral if every coordinate lies in $\{0,1/2,1\}$. Half-integral solutions are combinatorially rigid — their fractional ($1/2$-valued) edges form a structured union of cycles — and every known worst-case example for the subtour LP is half-integral. Schalekamp, Williamson and van Zuylen proved the Boyd–Carr conjecture that the worst-case ratio of an optimal 2-matching (an integral solution obeying only the degree constraints, i.e. a spanning collection of vertex-disjoint cycles) to the subtour LP is $10/9$, and were led to conjecture that the integrality gap of the subtour LP is itself attained on half-integral vertices of the subtour polytope (the feasible region of the subtour LP).

The source paper proved the first better-than-$3/2$ guarantee on half-integral instances: given any half-integral solution $x$ of the subtour LP, sample a spanning tree from the maximum-entropy distribution over spanning trees whose marginal edge probabilities equal $x$ (the unique such distribution that is as uniform as possible), then correct parities by adding a minimum-cost perfect matching on the odd-degree vertices; the output tour has expected cost at most $1.49993\,c(x)$, in randomized polynomial time. The analysis is a global amortized charging argument over the hierarchy of near-minimum cuts (cuts of LP value in $[2,2+\epsilon]$), with a universal constant $p\ge 1/27$ and a per-edge expected gain $p/240$; the authors identify the more complex structure of near-minimum cuts for non-half-integral solutions as the main barrier to extending the analysis. Consequently, if the Schalekamp–Williamson–van Zuylen conjecture holds, the integrality gap of the subtour LP is at most the best half-integral guarantee — $1.49776$ as of 2025. In the same line of work, the same authors later obtained a randomized $3/2-\epsilon$ approximation for all metric instances ($\epsilon>10^{-36}$), so the general integrality gap is also known to be below $3/2$. The half-integral supremum is known to lie in $[4/3,1.49776]$ and the general gap in $[4/3,3/2-\epsilon]$.

Problem Statement

The problem is the Schalekamp–Williamson–van Zuylen half-integrality conjecture for the subtour LP, posed at the conclusion of their proof of the Boyd–Carr conjecture (in the original form: the worst-case integrality gap is achieved at costs for which an optimal solution of the subtour LP is also an optimal fractional 2-matching, i.e. instances for which adding the subtour-elimination constraints leaves the LP optimal value unchanged) and stated as Conjecture 1.1 of the source paper:

The integrality gap for the subtour LP is attained on half-integral vertices of the polytope.

Equivalently, in supremum form:

$$\sup_{I}\;\frac{\mathrm{OPT}(I)}{\mathrm{LP}(I)}\;\stackrel{?}{=}\;\sup_{I_{\mathrm{HI}}}\;\frac{\mathrm{OPT}(I_{\mathrm{HI}})}{\mathrm{LP}(I_{\mathrm{HI}})}$$

where $I$ ranges over all finite symmetric metric TSP instances (arbitrarily many vertices), $I_{\mathrm{HI}}$ over those whose subtour LP optimum is attained at a half-integral vertex, $\mathrm{OPT}$ denotes the optimal tour cost and $\mathrm{LP}$ the optimal subtour LP value. The half-integral supremum is known to lie in $[4/3,1.49776]$ and the general gap in $[4/3,3/2-\epsilon]$ for some $\epsilon>10^{-36}$, so the two sides have not been separated. The conjecture is logically weaker than the four-thirds conjecture (a gap of exactly $4/3$ would imply it, since half-integral envelope families already attain $4/3$), and refuting it would mean exhibiting metric instances whose integrality ratio exceeds the half-integral supremum — necessarily exceeding $4/3$, and hence simultaneously refuting the four-thirds conjecture.

References

1. Anna Karlin, Nathan Klein, Shayan Oveis Gharan. An Improved Approximation Algorithm for TSP in the Half Integral Case. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). DOI: 10.1145/3357713.3384273. Preprint arXiv:1908.00227 (2019), DOI: 10.48550/arXiv.1908.00227. https://arxiv.org/abs/1908.00227
2. Frans Schalekamp, David P. Williamson, Anke van Zuylen. 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture. Mathematics of Operations Research 39(2):403-417 (2014). DOI: 10.1287/moor.2013.0608. Preprint arXiv:1107.1628. https://arxiv.org/abs/1107.1628
3. 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). DOI: 10.1145/3406325.3451009. Journal version: Operations Research 72:2543-2594 (2024). DOI: 10.1287/opre.2022.2338. Preprint arXiv:2007.01409 (2020), DOI: 10.48550/arXiv.2007.01409. https://arxiv.org/abs/2007.01409
4. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022). DOI: 10.1109/focs54457.2022.00084. Preprint arXiv:2105.10043 (2021), DOI: 10.48550/arXiv.2105.10043. https://arxiv.org/abs/2105.10043
5. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan. A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. arXiv:2212.06296 (2022). DOI: 10.48550/arXiv.2212.06296. https://arxiv.org/abs/2212.06296
6. Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar. Matroid-based TSP rounding for half-integral solutions. Mathematical Programming 206(1-2):541-576 (2024). DOI: 10.1007/s10107-024-02065-4. Preprint arXiv:2111.09290. https://arxiv.org/abs/2111.09290
7. Nathan Klein, Mehrshad Taziki. Dual Charging for Half-Integral TSP. arXiv:2507.17999 (2025). DOI: 10.48550/arXiv.2507.17999. https://arxiv.org/abs/2507.17999
8. 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. Preprint arXiv:2211.04639 (2022), DOI: 10.48550/arXiv.2211.04639. https://arxiv.org/abs/2211.04639
9. Billy Jin, Nathan Klein, David P. Williamson. A Lower Bound for the Max Entropy Algorithm for TSP. Integer Programming and Combinatorial Optimization (IPCO 2024), Lecture Notes in Computer Science. DOI: 10.1007/978-3-031-59835-7_18. Journal version: Mathematical Programming 216:425-447 (2025). DOI: 10.1007/s10107-025-02289-y. Preprint arXiv:2311.01950 (2023), DOI: 10.48550/arXiv.2311.01950. https://arxiv.org/abs/2311.01950
10. 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 69:107493 (2026). DOI: 10.1016/j.orl.2026.107493. Preprint arXiv:2607.01536 (2026), DOI: 10.48550/arXiv.2607.01536. https://arxiv.org/abs/2607.01536
11. S. Boyd, J. Cheriyan, R. Cummings, L. Grout, S. Ibrahimpur, Z. Szigeti, L. Wang. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. SIAM Journal on Discrete Mathematics 36(3):1730-1747 (2022). DOI: 10.1137/20m1372822. Preprint arXiv:2008.03327 (2020), DOI: 10.48550/arXiv.2008.03327. https://arxiv.org/abs/2008.03327
12. William Cook, Stefan Hougardy, Moritz Petrich. Extending Exact Integrality Gap Computations for the Metric TSP. arXiv:2603.12995 (2026). DOI: 10.48550/arXiv.2603.12995. https://arxiv.org/abs/2603.12995
13. Toshiaki Yamanaka. TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima. arXiv:2511.11215 (2025). DOI: 10.48550/arXiv.2511.11215. https://arxiv.org/abs/2511.11215
14. 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). DOI: 10.48550/arXiv.2507.07003. https://arxiv.org/abs/2507.07003
15. 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. Preprint arXiv:2102.04765. https://arxiv.org/abs/2102.04765