Math Conjectures

Metric-TSP subtour-LP 4/34/3 conjecture

OPENLandmarkConjectureProposed c. 1980 · Full conjecture

Canonical statement

For every integer n≥3n\ge3, let Kn=(V,E)K_n=(V,E), and let c:E→R≥0c:E\to\mathbb R_{\ge0} satisfy c{u,v}≤c{u,w}+c{w,v}c_{\{u,v\}}\le c_{\{u,w\}}+c_{\{w,v\}} for all distinct u,v,wu,v,w. Let TSP⁡(c)\operatorname{TSP}(c) be the minimum cc-length of a Hamilton cycle, and define
HK⁡(c)=min⁡{∑e∈Ecexe:xe≥0, ∑e∈δ(v)xe=2 (v∈V), ∑e∈δ(S)xe≥2 (∅≠S⊊V)}, \operatorname{HK}(c)=\min\left\{\sum_{e\in E}c_ex_e:x_e\ge0,\ \sum_{e\in\delta(v)}x_e=2\ (v\in V),\ \sum_{e\in\delta(S)}x_e\ge2\ (\varnothing\ne S\subsetneq V)\right\},
where δ(S)\delta(S) is the set of edges having exactly one endpoint in SS. Then, with the supremum restricted to instances satisfying HK⁡(c)>0\operatorname{HK}(c)>0,
sup⁡n,cTSP⁡(c)HK⁡(c)=43. \sup_{n,c}\frac{\operatorname{TSP}(c)}{\operatorname{HK}(c)}=\frac43.
View source LaTeX
For every integer \(n\ge3\), let \(K_n=(V,E)\), and let \(c:E\to\mathbb R_{\ge0}\) satisfy \(c_{\{u,v\}}\le c_{\{u,w\}}+c_{\{w,v\}}\) for all distinct \(u,v,w\). Let \(\operatorname{TSP}(c)\) be the minimum \(c\)-length of a Hamilton cycle, and define
\[
\operatorname{HK}(c)=\min\left\{\sum_{e\in E}c_ex_e:x_e\ge0,\ \sum_{e\in\delta(v)}x_e=2\ (v\in V),\ \sum_{e\in\delta(S)}x_e\ge2\ (\varnothing\ne S\subsetneq V)\right\},
\]
where \(\delta(S)\) is the set of edges having exactly one endpoint in \(S\). Then, with the supremum restricted to instances satisfying \(\operatorname{HK}(c)>0\),
\[
\sup_{n,c}\frac{\operatorname{TSP}(c)}{\operatorname{HK}(c)}=\frac43.
\]
OR-001:[Wolsey1980TSP][KarlinKleinOveisGharan2023TSP][TraubVygen2024TSP]
Operations researchMathematical optimization

Notes

For a metric travelling salesman instance, the Held–Karp (subtour) relaxation replaces Hamilton cycles by fractional edge values satisfying the degree and cut constraints. The conjecture asserts that the worst-case ratio between the length of an optimal tour and the optimal value of this linear program–the integrality gap–is exactly 4/34/3. The sharp prediction emerged around 1980 from early work linking heuristic analysis, linear programming, and the subtour relaxation [Wolsey1980TSP], rather than from a single dated proposal.

One direction is classical: families of metric instances are known whose ratio tends to 4/34/3, so the conjectured value cannot be lowered. In the other direction, Wolsey's analysis bounds the gap by 3/23/2 [Wolsey1980TSP], a barrier that stood for four decades until Karlin, Klein, and Oveis Gharan improved the guarantee to 3/2−ε3/2-\varepsilon for a very small absolute constant ε>0\varepsilon>0 [KarlinKleinOveisGharan2023TSP]. The surrounding theory is surveyed by Traub and Vygen [TraubVygen2024TSP].

The conjecture remains open; a proof would require certifying, on every metric instance, a tour of length within 4/34/3 of the relaxation value.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.