The Integrality Gap of the Traveling Salesman Problem is $\frac{4}{3}$ if the LP Solution Has at Most n + 6 Non-Zero Components

Tullio Villa, Eleonora Vercesi, János Barta, Monaldo Mastrolilli

TL;DR

This paper tackles the long-standing "integrality gap" problem in the Traveling Salesman Problem (TSP), specifically focusing on the Dantzig-Fulkerson-Johnson (DFJ) formulation. The authors prove that the integrality gap is $\frac{4}{3}$ for a significant class of TSP instances: those where the optimal solution to the linear relaxation (Subtour Elimination Problem, SEP) has at most $n+6$ non-zero components. This result, achieved through a novel combination of theoretical analysis and computational verification, provides strong evidence for a long-standing conjecture in the field.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem where a salesman must visit a set of cities exactly once and return to the starting city, minimizing the total travel distance. A common approach to solving TSP is to formulate it as an Integer Linear Program (ILP). However, ILPs are generally hard to solve. A relaxation of the ILP, known as the Linear Program (LP), is often easier to solve but its solution might not be an integer, meaning it doesn't directly correspond to a valid TSP tour. The "integrality gap" measures how much worse the optimal LP solution is compared to the optimal ILP solution. For the symmetric metric TSP, the DFJ formulation's LP relaxation is called the Subtour Elimination Problem (SEP). A major open question has been to determine the maximum possible integrality gap, with a conjecture that it is $\frac{4}{3}$. This paper addresses this by proving the $\frac{4}{3}$ conjecture for a specific, yet rich, subset of TSP instances.

Methods

The paper introduces a novel methodology that combines theoretical analysis with computational verification. Key elements include:

  • The Gap-Bounding (GB) Algorithm: This algorithm is designed to provide an upper bound on the integrality gap for a given vertex of the subtour elimination polytope. It leverages dual formulations of related optimization problems (OPT+ and OPTII) and a recursive construction of successors.
  • Ancestor and Successor Concepts: To manage the infinite nature of the problem space, the authors define "ancestors" (vertices of a specific family that cannot be obtained by a simple transformation) and "successors" (vertices derived from ancestors through a series of "BB-moves"). This allows them to analyze a finite set of representative vertices.
  • BB-Move: This is a specific operation that adds a new node to the graph and modifies the solution, allowing for the generation of new vertices and the exploration of the solution space.
  • Computational Verification: The GB algorithm is implemented and run on a carefully selected set of ancestors and their successors. This computational aspect is crucial for verifying the theoretical bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and computational verification on generated instances derived from the structure of the subtour elimination polytope.

Key Insights and Ideas

  • The $n+6$ Threshold is Key: The paper's main contribution is proving the $\frac{4}{3}$ integrality gap for instances where the optimal SEP solution has at most $n+6$ non-zero components. This specific bound on the number of non-zero components is critical for the theoretical framework.
  • A New Computational Proof Paradigm: The work demonstrates the power of combining theoretical analysis with computational methods to tackle complex problems like the integrality gap. This approach allows for proofs that are not limited to fixed small instances but can extend to infinite families of vertices.
  • The "Few Edges Hypothesis": The authors propose a hypothesis that the maximum integrality gap is likely achieved on vertices with the minimum possible number of edges in their support graph (specifically, $n+3$). This, combined with their current work, could lead to a definitive resolution of the $\frac{4}{3}$ conjecture.
  • Correlation between Support Graph Size and Gap: Empirical observations suggest a correlation: vertices with fewer non-zero components (smaller support graphs) tend to have larger integrality gaps. This observation motivates further research into the structure of these "hard" instances.

Key Results

  • The paper proves that the integrality gap of the symmetric metric TSP is $\frac{4}{3}$ if the optimal LP solution (SEP) has at most $n+6$ non-zero components. This applies to a large and previously unaddressed class of vertices of the subtour elimination polytope.
  • A novel Gap-Bounding (GB) algorithm is developed and implemented, which provides an upper bound on the integrality gap.
  • Computational results confirm that the GB algorithm, when applied to ancestors and selected successors for $k=3,4,5,6$ (where $k$ relates to the number of edges beyond the minimum $n+3$), yields upper bounds of $\frac{4}{3}$ for the integrality gap.

Limitations and Future Work

  • Focus on $n+6$: While significant, the result is conditional on the number of non-zero components in the LP solution. The paper does not prove the $\frac{4}{3}$ conjecture for all TSP instances.
  • "Few Edges Hypothesis" Verification: The paper proposes the "Few Edges Hypothesis" and suggests that proving it would definitively solve the $\frac{4}{3}$ conjecture. This remains an open research direction.
  • Exploring $F_7$ and beyond: The authors suggest extending their analysis to $k=7$ and beyond by enumerating more ancestors.
  • Investigating the Correlation: Further research is needed to formally investigate the observed correlation between the number of edges in the support graph and the integrality gap.
  • Generalizing the GB Algorithm: The methodology of the GB algorithm could potentially be adapted to analyze integrality gaps in other combinatorial optimization problems.

Summary updated

BibTeX
@inproceedings{villa2026integrality,
  author = {Tullio Villa and Eleonora Vercesi and János Barta and Monaldo Mastrolilli},
  title = {{The Integrality Gap of the Traveling Salesman Problem is $\textbackslash\{\}frac\{4\}\{3\}$ if the LP Solution Has at Most n + 6 Non-Zero Components}},
  booktitle = {IPCO},
  year = {2026},
  doi = {10.1007/978-3-032-28691-8\_9},
}
Figure