{"id":"arxiv/2603.12995","url":"https://arxiv.org/abs/2603.12995","tags":["math.CO","cs.DS"],"score":0,"title":"Extending Exact Integrality Gap Computations for the Metric TSP","domain":"math.CO","source":"arxiv","authors":["William Cook","Stefan Hougardy","Moritz Petrich"],"reviews":0,"subject":"math.CO","summary":"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 to a larger number 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-13","reactions":{}}