Metric TSP Subtour LP Integrality Gap Conjecture

Metric TSP Subtour LP Integrality Gap Conjecture

Definitions and mathematical statement

For a complete graph on $n\ge3$ vertices with nonnegative symmetric edge costs satisfying the triangle inequality, let $\mathrm{OPT}_{\mathrm{TSP}}$ be the minimum Hamiltonian-cycle cost. The subtour relaxation minimizes $\sum_e c_ex_e$ subject to \[ x(\delta(v))=2\quad(v\in V),\qquad x(\delta(S))\ge2\quad(\varnothing\ne S\subsetneq V),\qquad x_e\ge0. \] Here $\delta(S)$ is the edge cut and $x(F)=\sum_{e\in F}x_e$. The integrality gap is the supremum of $\mathrm{OPT}_{\mathrm{TSP}}/\mathrm{OPT}_{\mathrm{LP}}$ over positive-denominator metric instances. Determine whether this supremum is exactly $4/3$. The target covers all symmetric metrics, not only costs one and two used in the cited paper's special case.

Formulation and concept references: [S1].

Short English statement

Is the true optimal metric traveling-salesman tour always within a factor four-thirds of the subtour linear-programming bound, with that factor sharp?

Research attempt

Current frontier.

Karlin--Klein--Oveis Gharan establish an upper bound strictly below $3/2$ for the general subtour integrality gap; their Theorem 1.1 permits an improvement exceeding $10^{-36}$. This is distinct from the $1,2$-metric special case in the catalogue's source. [E1], [S1]. A relevant negative result is Jin--Klein--Williamson's lower bound of $11/8$ on the approximation ratio of the maximum-entropy algorithm, even for graphic TSP. It is a barrier to that algorithm, not a lower bound of $11/8$ on the LP integrality gap. [E2].

Attack route.

Rather than seek another marginal estimate for the unchanged maximum-entropy algorithm, allow metric triangle inequalities to enter the rounding certificate explicitly. The desired certificate need not be coordinatewise domination of a convex combination of tours. We first derive an exact metric-cone formulation, then test it against a near-$4/3$ family. A constructive proof of this certificate for every subtour vector would prove the upper bound; an LP separator outside the cone would instead give a metric counterexample.

Attempt.

1. A metric-aware certificate. For a fixed vertex set let $\mathcal T$ be the convex hull of Hamiltonian cycle incidence vectors in ${\mathbb{R}}^E$. Let $\mathcal M$ be the closed polyhedral cone of nonnegative symmetric metrics, including pseudometrics. Write its dual with the positive convention: \[ \mathcal M^*=\{z:c\cdot z\ge0\text{ for every }c\in\mathcal M\}. \] If $e_{ij}$ denotes the coordinate vector of edge $ij$, the defining inequalities for $\mathcal M$ give \[ \mathcal M^*=\operatorname{cone} \{e_{ij},\ e_{ik}+e_{kj}-e_{ij}: i,j,k\text{ distinct}\}. \] This follows from finite-dimensional polyhedral duality, or directly from Farkas' lemma applied to the displayed defining inequalities. For any fixed feasible subtour vector $x$ and $\alpha>0$, \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-37-38-37-3a-64-75-61-6c} \min_{t\in\mathcal T}c\cdot t\le\alpha c\cdot x \quad\text{for every }c\in\mathcal M \quad\Longleftrightarrow\quad \alpha x\in\mathcal T+\mathcal M^*. \end{equation} To prove the nontrivial implication, $\mathcal T+\mathcal M^*$ is closed and convex: $\mathcal T$ is compact, so a convergent sequence of sums has a subsequence whose first terms converge. If $\alpha x$ is outside it, strong separation gives a vector $c$ with $c\cdot\alpha x<\inf_{t,z}c\cdot(t+z)$. Finiteness of the infimum forces $c\cdot z\ge0$ for all $z\in\mathcal M^*$, hence $c\in\mathcal M$. The infimum then equals $\min_{t\in\mathcal T}c\cdot t$, contradicting the left side. The reverse implication follows immediately by taking scalar products.

Thus a sufficient and, collectively for all feasible $x$, necessary certificate at $4/3$ is \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-37-38-37-3a-63-65-72-74-69-66-69-63-61-74-65} \frac43 x=\sum_T\lambda_T\chi_T+s+ \sum_{i,j,k}\mu_{ijk}(e_{ik}+e_{kj}-e_{ij}), \qquad \lambda_T,\mu_{ijk},s_e\ge0,\quad\sum_T\lambda_T=1. \end{equation} There is no requirement to list exponentially many tours: ordinary convex and conic Carathéodory reductions give finite supports of size bounded in terms of $|E|$. They do not provide a polynomial-time algorithm to find those supports. The negative coordinate in a triangle normal is intentional; replacing $\mathcal M^*$ by the nonnegative orthant is a stronger assertion not proved equivalent here.

The original positive-denominator restriction causes no discrepancy. If a metric has LP value zero, the positive support of a zero-cost feasible vector is connected, by the cut constraints. Its edges have zero cost; the triangle inequality along paths then makes every pair have distance zero. Its tour value is therefore zero as well. Conversely, assuming the gap upper bound for every metric and choosing an LP optimum yields the left side of (eq:30006787:dual) for every feasible $x$, because $c\cdot x$ is at least the LP optimum.

2. Reconstructing a sharp lower-limit obstruction. Take two disjoint triangles with vertices $a_1,a_2,a_3$ and $b_1,b_2,b_3$. Join $a_i$ to $b_i$ by a path of $L\ge1$ unit edges, the three paths having disjoint interiors. Give the complete graph on these $n=3L+3$ vertices its shortest-path metric. Put $x_e=1$ on the three paths, $x_e=1/2$ on both triangles, and zero on the other edges. Every vertex has $x$-degree two.

For completeness check every cut, not only the pictured ones. A cut crossing at least two path edges has weight at least two. A cut crossing no path edges is a nonempty proper union of entire paths; each endpoint triangle then contributes one. If exactly one path edge crosses, at least one endpoint triangle must be cut. Otherwise all three $a_i$ lie on one side and all three $b_i$ on one side; parity would force either zero or at least three path crossings, not one. A cut triangle contributes one, so this case also has weight at least two. Thus $x$ is feasible with cost $3L+3=n$. Since every nonzero distance is at least one and every feasible vector has $\sum_e x_e=n$, \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-37-38-37-3a-6c-6f-77-65-72-6c-70} \mathrm{OPT}_{\mathrm{LP}}=3L+3. \end{equation}

Expand a metric Hamiltonian cycle into shortest paths in this graph. The resulting connected spanning Eulerian multigraph has the same cost. At each internal path vertex the two incident edge multiplicities have the same parity. Call a path odd or even accordingly. The number of odd paths is even, since it is the parity of the cut leaving an endpoint triangle. It is therefore zero or two. An odd path costs at least $L$. An even path may omit at most one edge: two omitted edges would disconnect an internal vertex or segment from the connected spanning multigraph. Its cost is at least $2(L-1)$. If all three paths are even, at least one is unbroken to connect the two triangles and costs at least $2L$. Hence path costs alone imply \[ \mathrm{OPT}_{\mathrm{TSP}}\ge \min\{L+L+2(L-1),\;2L+4(L-1)\}=4L-2. \] For an upper comparison, take two paths once, the third path twice except for one omitted edge, and in each triangle take the two-edge path joining the endpoints of the odd paths through the third vertex. This is connected and Eulerian, costs $4L+2$, and can be shortcut to a Hamiltonian tour. Consequently \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-37-38-37-3a-6c-69-6d-69-74} \frac{4L-2}{3L+3}\le \frac{\mathrm{OPT}_{\mathrm{TSP}}}{\mathrm{OPT}_{\mathrm{LP}}} \le\frac{4L+2}{3L+3},\qquad \text{ratio}\longrightarrow\frac43. \end{equation} This is a reconstruction of the familiar type of lower-bound family, not a claim of a newly discovered integrality-gap example. The checking script verifies every cut and computes exact tours for the first three members; the proof above covers all $L$.

Stress test.

Coordinatewise rounding can waste the freedom to replace a long edge by a two-edge path whose metric cost is larger. Conversely, arbitrary signed corrections are not legitimate: the correction must lie in the specific dual cone in (eq:30006787:certificate). The certificate does not follow from the subtour inequalities by an unproved application of Farkas' lemma; those inequalities define $x$, whereas the as-yet-unknown tour combination is the essential issue.

The sharp-family calculation establishes only the lower limit. It does not produce a universal certificate and cannot rule out other metrics with ratio greater than $4/3$. Nor can the remaining step simply be outsourced to a sharper analysis of the same maximum-entropy algorithm: its $11/8$ obstruction lies strictly above $4/3$. That theorem does not exclude different distributions, additional reconnection operations, or the metric-cone certificate proposed here. [E2].

Outcome.

Outcome: Conditional reduction. The upper-bound problem is equivalent to the explicit family of metric-cone certificates (eq:30006787:certificate). An all-$L$ argument also recovers the lower bound $4/3$ for the supremum. What remains unproved is existence of the certificates for every feasible subtour vector, or a separating metric showing their failure. Finite tests and the known lower-bound family do not resolve that universal question.

Sources

• S1 J. Qian, F. Schalekamp, D. P. Williamson, A. van Zuylen, On the integrality gap of the subtour LP for the 1,2-TSP, Math. Program. 148 $2014$ 411-417. https://doi.org/10.1007/s10107-014-0835-4. Catalogue formulation source.
• E1 Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, arXiv:2105.10043v3. Theorem 1.1 is the general LP integrality-gap theorem, not merely a guarantee relative to the optimal tour. https://arxiv.org/html/2105.10043v3. Research reference; consulted 27 September 2026.
• E2 Billy Jin, Nathan Klein, and David P. Williamson, A Lower Bound for the Max Entropy Algorithm for TSP, arXiv:2311.01950v2; Mathematical Programming 216 $2026$, 425--447. Main $11/8$ algorithmic lower bound and the distinction from the subtour LP gap. https://arxiv.org/html/2311.01950v2. Research reference; consulted 27 September 2026.