Extending Exact Integrality Gap Computations for the Metric TSP

Moritz Petrich; Stefan Hougardy; William Cook

arxiv: 2603.12995 · v3 · submitted 2026-03-13 · 🧮 math.CO · cs.DS

Extending Exact Integrality Gap Computations for the Metric TSP

William Cook , Stefan Hougardy , Moritz Petrich This is my paper

Pith reviewed 2026-05-15 12:14 UTC · model grok-4.3

classification 🧮 math.CO cs.DS

keywords subtour polytopeintegrality gapmetric TSPextreme points4/3 conjecturetraveling salesman problempolyhedral combinatoricsenumeration

0 comments

The pith

The subtour relaxation for the metric TSP has an integrality gap of at most 4/3 for all instances with up to 14 vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends the exact computation of the integrality gap of the subtour polytope for small metric TSP instances. By enumerating all extreme points up to 14 vertices in general and up to 17 for half-integral cases, it corrects earlier incomplete lists for 11 and 12 vertices. These calculations confirm that the gap never exceeds 4/3 in these cases. The results add evidence to the conjecture that 4/3 is the exact gap for all metric instances, regardless of size.

Core claim

The authors use the Benoit and Boyd enumeration framework to list all extreme points of the subtour polytope for n from 11 to 14, finding one missing point for n=11 and 22 for n=12. For each such point, they compute the maximum integrality gap over metric completions, and find it is at most 4/3, with equality attained. Half-integral extreme points are enumerated up to n=17 with the same result.

What carries the argument

The extreme points of the subtour polytope, whose convex combination represents feasible fractional solutions, with the ratio of the TSP optimum to the subtour value determining the gap for each point.

Load-bearing premise

The enumeration algorithm correctly identifies every extreme point of the subtour polytope for the given sizes without omissions or errors in the search process.

What would settle it

A metric TSP instance on 14 vertices where the shortest tour length exceeds 4/3 times the value of the subtour LP relaxation, or an undiscovered extreme point for n=14 with a higher ratio.

read the original abstract

The subtour relaxation of the traveling salesman problem (TSP) plays a central role in approximation algorithms and polyhedral studies of the TSP. A long-standing conjecture asserts that the integrality gap of the subtour relaxation for the metric TSP is exactly 4/3. In this paper, we extend the exact verification of this conjecture for small numbers of vertices. Using the framework introduced by Benoit and Boyd in 2008, we confirm their results up to n=10. We further show that for n=11 and n=12, the published lists of extreme points of the subtour polytope are incomplete: one extreme point is missing for n=11 and twenty-two extreme points are missing for n=12. We extend the enumeration of the extreme points of the subtour polytope to instances with up to 14 vertices in the general case. Restricted to half-integral vertices, we extend the enumeration of extreme points up to n=17. Our results provide additional support for the 4/3-Conjecture. Our lists of extreme points are available on the public bonndata repository (https://doi.org/10.60507/FK2/JK95PC).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends the known extreme points of the subtour polytope to n=14 (and half-integral to n=17), corrects prior omissions for n=11 and 12, and adds small-n support for the 4/3 gap.

read the letter

The paper's real contribution is a corrected and extended list of extreme points for the subtour polytope. Using the Benoit-Boyd 2008 framework, they verify everything through n=10, then locate one missing point at n=11 and twenty-two at n=12. They push the full enumeration to n=14 and the half-integral case to n=17. The lists are deposited publicly on bonndata, so the output can be inspected directly. That is the concrete advance: new points and a longer verified range rather than a new proof technique or algorithmic result. It supplies additional small-instance evidence that no extreme point exceeds the 4/3 gap, which is useful incremental data for anyone studying the metric TSP integrality conjecture. The work is honest about what it does; it does not claim to settle the conjecture or change practice for large instances. The main limitation is that completeness still depends on the correctness of their implementation of the 2008 procedure. The fact that they recovered the previously missed points is evidence the code is running properly, but there is no independent solver cross-check or machine-checked certificate. For computational enumeration papers this is common, yet it means a missed point with larger gap remains a theoretical possibility, even if unlikely given the corrections they already made. The citation pattern is appropriate; they build directly on the prior literature without circularity. This is a paper for people already working on TSP polyhedra or exact integrality-gap computations. A general reader in approximation algorithms will find little new, but specialists can use the lists to test conjectures or seed further searches. It is solid enough to deserve referee time: the claims are narrow, the data is public, and the corrections to earlier lists are a clear improvement over the status quo.

Referee Report

1 major / 0 minor

Summary. The manuscript extends exact integrality-gap computations for the metric TSP subtour relaxation by enumerating extreme points of the subtour polytope. Using the Benoit-Boyd 2008 framework, the authors confirm all prior results through n=10, identify one missing extreme point for n=11 and twenty-two for n=12, and produce complete lists up to n=14 in the general case and n=17 when restricted to half-integral vertices. The resulting data are deposited publicly and are claimed to furnish additional support for the 4/3-conjecture.

Significance. If the enumerations are exhaustive, the work supplies concrete computational evidence for the 4/3-conjecture by pushing the verified range beyond previous limits and correcting documented omissions in the literature. The public deposition of the extreme-point lists on the bonndata repository is a clear strength, enabling independent verification and further polyhedral analysis.

major comments (1)

The central claim that the new lists for n=11–14 (and half-integral n=17) are complete rests on the authors’ implementation of the Benoit-Boyd enumeration procedure. While the manuscript confirms agreement with prior lists up to n=10 and reports the specific omissions it found, it provides no explicit termination argument, search-space exhaustion criterion, or pseudocode demonstrating that every vertex of the subtour polytope has been generated. Because the same framework previously missed points, this verification gap is load-bearing for the completeness assertion that underpins the support claimed for the 4/3-conjecture.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater transparency in our computational procedure. We address the single major comment below.

read point-by-point responses

Referee: The central claim that the new lists for n=11–14 (and half-integral n=17) are complete rests on the authors’ implementation of the Benoit-Boyd enumeration procedure. While the manuscript confirms agreement with prior lists up to n=10 and reports the specific omissions it found, it provides no explicit termination argument, search-space exhaustion criterion, or pseudocode demonstrating that every vertex of the subtour polytope has been generated. Because the same framework previously missed points, this verification gap is load-bearing for the completeness assertion that underpins the support claimed for the 4/3-conjecture.

Authors: We agree that the manuscript would be strengthened by an explicit description of the termination and exhaustion criteria. In the revised version we will add a new subsection that (i) recalls the precise search-space reduction steps from the Benoit-Boyd framework, (ii) states the finite termination criterion (exhaustive enumeration of all candidate supports satisfying the subtour inequalities up to the known dimension bound), and (iii) supplies concise pseudocode for the core generation-and-verification loop. Because our implementation reproduces every previously published extreme point through n=10 and recovers the additional points for n=11 and n=12, the same exhaustive procedure is used for the larger instances; the added documentation will make this argument self-contained. revision: yes

Circularity Check

0 steps flagged

No circularity in enumeration results

full rationale

The paper performs independent computational enumeration of extreme points of the subtour polytope by extending the Benoit and Boyd 2008 framework. It confirms results to n=10, corrects omissions for n=11 and 12, and extends the lists to n=14 (general) and n=17 (half-integral), with all lists made publicly available. No step reduces by definition to its inputs, no fitted parameters are renamed as predictions, and the cited framework is from independent prior authors. The derivation is self-contained and externally verifiable via the released data.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper extends the standard definition of the subtour polytope and the Benoit and Boyd enumeration framework without introducing new free parameters or invented entities.

axioms (1)

standard math The subtour polytope is the convex hull of the incidence vectors of tours satisfying the degree and subtour elimination constraints.
This is the standard polyhedral formulation of the TSP subtour relaxation used throughout the literature.

pith-pipeline@v0.9.0 · 5508 in / 1282 out tokens · 49246 ms · 2026-05-15T12:14:35.306760+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

A revised implementation of the reverse search vertex enumeration algorithm

David Avis. A revised implementation of the reverse search vertex enumeration algorithm. In Gil Kalai and G¨ unter M. Ziegler, editors,Polytopes - Combinatorics and Computation, DMV Seminar, vol 29., pages 177–198. Birkh¨ auser, 2000.doi: 10.1007/978-3-0348-8438-9_9. 5

work page doi:10.1007/978-3-0348-8438-9_9 2000
[2]

Hill, and Enea Zaffanella

Roberto Bagnara, Patricia M. Hill, and Enea Zaffanella. The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and ver- ification of hardware and software systems.Science of Computer Programming, 72(1–2):3–21, 2008.doi:10.1016/j.scico.2007.08.001

work page doi:10.1016/j.scico.2007.08.001 2008
[3]

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

Genevi` eve Benoit and 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

work page doi:10.1287/moor.1080.0337 2008
[4]

Vertices of the subtour elimination polytope, 2011

Sylvia Boyd. Vertices of the subtour elimination polytope, 2011. URL: https:// www.site.uottawa.ca/∼sylvia/subtourvertices/index.htm

work page 2011
[5]

The traveling salesman problem on cubic and subcubic graphs.Mathematical Programming, Series A, 144:227–245, 2014.doi:10.1007/s10107-012-0620-1

Sylvia Boyd, Ren´ e Sitters, Suzanne van der Ster, and Leen Stougie. The traveling salesman problem on cubic and subcubic graphs.Mathematical Programming, Series A, 144:227–245, 2014.doi:10.1007/s10107-012-0620-1

work page doi:10.1007/s10107-012-0620-1 2014
[6]

Structure of the extreme points of the subtour elimination polytope of the STSP.RIMS Kˆ okyˆ uroku Bessatsu, B23:33–47, 2010

Sylvia Boyd and Paul Elliott-Magwood. Structure of the extreme points of the subtour elimination polytope of the STSP.RIMS Kˆ okyˆ uroku Bessatsu, B23:33–47, 2010

work page 2010
[7]

Normaliz

Winfried Bruns, Bogdan Ichim, Christof S¨ oger, and Ulrich von der Ohe. Normaliz. Algorithms for rational cones and affine monoids. Available at https://normaliz.uos. de

work page
[8]

The power of pyramid de- composition in Normaliz.Journal of Symbolic Computation, 74:513–536, 2016

Winfried Bruns, Bogdan Ichim, and Christof S¨ oger. The power of pyramid de- composition in Normaliz.Journal of Symbolic Computation, 74:513–536, 2016. doi:10.1016/j.jsc.2015.09.003

work page doi:10.1016/j.jsc.2015.09.003 2016
[9]

Vertices of the subtour poly- tope, 2026.doi:10.60507/FK2/JK95PC

William Cook, Stefan Hougardy, and Moritz Petrich. Vertices of the subtour poly- tope, 2026.doi:10.60507/FK2/JK95PC

work page doi:10.60507/fk2/jk95pc 2026
[10]

Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP.Math- ematical Programming, 69:335–349, 1995.doi:10.1007/BF01585563

work page doi:10.1007/bf01585563 1995
[11]

Michel X. Goemans. Thinness spurs progress.OPTIMA, 90:12–14, 2012

work page 2012
[12]

On the integrality ratio of the subtour LP for Euclidean TSP

Stefan Hougardy. On the integrality ratio of the subtour LP for Euclidean TSP. Operations Research Letters, 42(8):495–499, 2014.doi:10.1016/j.orl.2014.08. 009

work page doi:10.1016/j.orl.2014.08 2014
[13]

Hard to solve instances of the Euclidean Traveling Salesman Problem.Mathematical Programming Computation, 13:51–74, 2021.doi:10.1007/s12532-020-00184-5

Stefan Hougardy and Xianghui Zhong. Hard to solve instances of the Euclidean Traveling Salesman Problem.Mathematical Programming Computation, 13:51–74, 2021.doi:10.1007/s12532-020-00184-5

work page doi:10.1007/s12532-020-00184-5 2021
[14]

Williamson

Billy Jin, Nathan Klein, and David P. Williamson. A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP.Mathematical Programming, Series B, 210:511–538, 2025.doi:10.1007/s10107-025-02193-5

work page doi:10.1007/s10107-025-02193-5 2025
[15]

Karlin, Nathan Klein, and Shayan Oveis Gharan

Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A deterministic better- than-3/2 approximation algorithm for metric TSP. In Alberto Del Pia and Volker Kaibel, editors,Integer Programming and Combinatorial Optimization (IPCO 2023), pages 261–274. Springer, 2023.doi:10.1007/978-3-031-32726-1_19

work page doi:10.1007/978-3-031-32726-1_19 2023
[16]

and Piperno, Adolfo , TITLE =

Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014.doi:10.1016/j.jsc.2013.09.003. 6

work page doi:10.1016/j.jsc.2013.09.003 2014
[17]

The integrality gap of the traveling salesman problem is 4/3 if the LP solution has at mostn+ 6 non-zero components, 2025.arXiv:2507.07003

Tullio Villa, Eleonora Vercesi, Janos Barta, and Monaldo Mastrolilli. The integrality gap of the traveling salesman problem is 4/3 if the LP solution has at mostn+ 6 non-zero components, 2025.arXiv:2507.07003

work page arXiv 2025
[18]

Analysis of the Held-Karp heuristic for the Traveling Sales- man Problem

David Paul Williamson. Analysis of the Held-Karp heuristic for the Traveling Sales- man Problem. Master’s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990

work page 1990
[19]

Lower bounds on the integraliy 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

Xianghui Zhong. Lower bounds on the integraliy 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. 7

work page doi:10.1016/j.dam.2024.12.029 2025

[1] [1]

A revised implementation of the reverse search vertex enumeration algorithm

David Avis. A revised implementation of the reverse search vertex enumeration algorithm. In Gil Kalai and G¨ unter M. Ziegler, editors,Polytopes - Combinatorics and Computation, DMV Seminar, vol 29., pages 177–198. Birkh¨ auser, 2000.doi: 10.1007/978-3-0348-8438-9_9. 5

work page doi:10.1007/978-3-0348-8438-9_9 2000

[2] [2]

Hill, and Enea Zaffanella

Roberto Bagnara, Patricia M. Hill, and Enea Zaffanella. The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and ver- ification of hardware and software systems.Science of Computer Programming, 72(1–2):3–21, 2008.doi:10.1016/j.scico.2007.08.001

work page doi:10.1016/j.scico.2007.08.001 2008

[3] [3]

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

Genevi` eve Benoit and 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

work page doi:10.1287/moor.1080.0337 2008

[4] [4]

Vertices of the subtour elimination polytope, 2011

Sylvia Boyd. Vertices of the subtour elimination polytope, 2011. URL: https:// www.site.uottawa.ca/∼sylvia/subtourvertices/index.htm

work page 2011

[5] [5]

The traveling salesman problem on cubic and subcubic graphs.Mathematical Programming, Series A, 144:227–245, 2014.doi:10.1007/s10107-012-0620-1

Sylvia Boyd, Ren´ e Sitters, Suzanne van der Ster, and Leen Stougie. The traveling salesman problem on cubic and subcubic graphs.Mathematical Programming, Series A, 144:227–245, 2014.doi:10.1007/s10107-012-0620-1

work page doi:10.1007/s10107-012-0620-1 2014

[6] [6]

Structure of the extreme points of the subtour elimination polytope of the STSP.RIMS Kˆ okyˆ uroku Bessatsu, B23:33–47, 2010

Sylvia Boyd and Paul Elliott-Magwood. Structure of the extreme points of the subtour elimination polytope of the STSP.RIMS Kˆ okyˆ uroku Bessatsu, B23:33–47, 2010

work page 2010

[7] [7]

Normaliz

Winfried Bruns, Bogdan Ichim, Christof S¨ oger, and Ulrich von der Ohe. Normaliz. Algorithms for rational cones and affine monoids. Available at https://normaliz.uos. de

work page

[8] [8]

The power of pyramid de- composition in Normaliz.Journal of Symbolic Computation, 74:513–536, 2016

Winfried Bruns, Bogdan Ichim, and Christof S¨ oger. The power of pyramid de- composition in Normaliz.Journal of Symbolic Computation, 74:513–536, 2016. doi:10.1016/j.jsc.2015.09.003

work page doi:10.1016/j.jsc.2015.09.003 2016

[9] [9]

Vertices of the subtour poly- tope, 2026.doi:10.60507/FK2/JK95PC

William Cook, Stefan Hougardy, and Moritz Petrich. Vertices of the subtour poly- tope, 2026.doi:10.60507/FK2/JK95PC

work page doi:10.60507/fk2/jk95pc 2026

[10] [10]

Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP.Math- ematical Programming, 69:335–349, 1995.doi:10.1007/BF01585563

work page doi:10.1007/bf01585563 1995

[11] [11]

Michel X. Goemans. Thinness spurs progress.OPTIMA, 90:12–14, 2012

work page 2012

[12] [12]

On the integrality ratio of the subtour LP for Euclidean TSP

Stefan Hougardy. On the integrality ratio of the subtour LP for Euclidean TSP. Operations Research Letters, 42(8):495–499, 2014.doi:10.1016/j.orl.2014.08. 009

work page doi:10.1016/j.orl.2014.08 2014

[13] [13]

Hard to solve instances of the Euclidean Traveling Salesman Problem.Mathematical Programming Computation, 13:51–74, 2021.doi:10.1007/s12532-020-00184-5

Stefan Hougardy and Xianghui Zhong. Hard to solve instances of the Euclidean Traveling Salesman Problem.Mathematical Programming Computation, 13:51–74, 2021.doi:10.1007/s12532-020-00184-5

work page doi:10.1007/s12532-020-00184-5 2021

[14] [14]

Williamson

Billy Jin, Nathan Klein, and David P. Williamson. A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP.Mathematical Programming, Series B, 210:511–538, 2025.doi:10.1007/s10107-025-02193-5

work page doi:10.1007/s10107-025-02193-5 2025

[15] [15]

Karlin, Nathan Klein, and Shayan Oveis Gharan

Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A deterministic better- than-3/2 approximation algorithm for metric TSP. In Alberto Del Pia and Volker Kaibel, editors,Integer Programming and Combinatorial Optimization (IPCO 2023), pages 261–274. Springer, 2023.doi:10.1007/978-3-031-32726-1_19

work page doi:10.1007/978-3-031-32726-1_19 2023

[16] [16]

and Piperno, Adolfo , TITLE =

Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014.doi:10.1016/j.jsc.2013.09.003. 6

work page doi:10.1016/j.jsc.2013.09.003 2014

[17] [17]

The integrality gap of the traveling salesman problem is 4/3 if the LP solution has at mostn+ 6 non-zero components, 2025.arXiv:2507.07003

Tullio Villa, Eleonora Vercesi, Janos Barta, and Monaldo Mastrolilli. The integrality gap of the traveling salesman problem is 4/3 if the LP solution has at mostn+ 6 non-zero components, 2025.arXiv:2507.07003

work page arXiv 2025

[18] [18]

Analysis of the Held-Karp heuristic for the Traveling Sales- man Problem

David Paul Williamson. Analysis of the Held-Karp heuristic for the Traveling Sales- man Problem. Master’s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990

work page 1990

[19] [19]

Lower bounds on the integraliy 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

Xianghui Zhong. Lower bounds on the integraliy 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. 7

work page doi:10.1016/j.dam.2024.12.029 2025