Id: arxiv/2611.17386 Url: https://arxiv.org/abs/2611.17386 Tags: cs.DM, math.CO Score: 0 Title: TSP instances that require exponentially many subtour elimination constraints Domain: cs.DM Source: arxiv Authors: Eleonora Vercesi, Austin Buchanan Reviews: 0 Subject: cs.DM Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-11 Page: https://delphi.science/r/arxiv/2611.17386 We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(Ω(φ^n)\), where \(φ\approx 1.618\) is the golden ratio. A node-splitting reduction gives metric instances with \(Ω(φ^{n/2})\) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require…