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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-13 Page: https://delphi.science/r/arxiv/2603.12995 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…