Two Algebraic Thresholds for Relaxations of Stable Metric TSP
Abstract
Bilu–Linial stability asks whether an optimal solution remains uniquely optimal after every independent multiplicative increase of the input costs by a prescribed factor. For symmetric metric TSP, every 1.8-stable instance is solvable in polynomial time, and both the subtour relaxation and the weaker degree-only cycle-cover relaxation are exact at that threshold. We give explicit algebraic lower bounds showing that exactness can fail substantially below 1.8. First, for every gamma < (8 - sqrt(13))/3 = 1.464816..., we construct a gamma-stable metric instance whose subtour relaxation is strictly cheaper than the optimal tour; this constant is the exact threshold of a natural uniform three-path family. Second, let beta = 1.696023173588... be the unique root in (3/2, 17/10) of q^6 - 28q^4 + 72q^3 - 35q^2 - 24q - 2. For every gamma < beta, an explicit ten-city parametric metric has a strictly cheaper integral cycle cover than its unique optimal tour, and beta is the exact degree-relaxation threshold of that family. What is separated here are the two lower bounds, not the two thresholds themselves: both are still known only to be at most 1.8. The proofs combine analytic exchange bounds with exact computer-assisted certificates over algebraic number fields. All metric, tour, and cycle-cover comparisons use integer or symbolic arithmetic; no floating-point comparison decides any claim. This record contains the manuscript and the complete, reproducible proof artifacts. Version 1.1.0 adds a declaration of generative AI use before the references and cites the concept DOI, which always resolves to the latest version. The mathematical content is unchanged.
