{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}