The Integrality Gap of the Traveling Salesman Problem is 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 a long-standing conjecture in the Traveling Salesman Problem (TSP): that the integrality gap (the ratio between the optimal integer solution and its linear programming relaxation) is at most 4/3. The authors prove this conjecture holds for a significant class of TSP instances where the optimal LP solution has a limited number of non-zero components (specifically, at most n+6 for an n-node problem). This is achieved through a novel combination of theoretical analysis and a computer-aided approach.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem where the goal is to find the shortest possible route that visits a set of cities and returns to the origin city. While TSP can be formulated as an Integer Linear Program (ILP), solving ILPs is generally NP-hard. A common approach is to relax the ILP to a Linear Program (LP) and solve that instead. The "integrality gap" measures how much worse the LP solution might be compared to the true optimal ILP solution. For the symmetric metric TSP, the Dantzig-Fulkerson-Johnson formulation's LP relaxation is known as the Subtour Elimination Problem (SEP). A major open question in the field has been to determine the maximum possible integrality gap for TSP. For decades, it has been conjectured that this gap is 4/3, but proving this for all possible instances has been elusive. This paper focuses on proving this 4/3 conjecture for a specific, yet substantial, subset of TSP instances.

Methods

The core of this paper's contribution lies in a novel methodology that combines theoretical insights with computational verification.

  • Theoretical Framework: The authors introduce the concept of "ancestors" of vertices in the subtour elimination polytope. These are vertices that cannot be obtained by a "BB-move" (a specific construction that adds nodes and edges). They then define families of vertices $F_k$ based on the number of edges in their support graph (i.e., edges with non-zero values in the LP solution). The key theoretical tool is the "Gap-Bounding (GB) algorithm," which aims to provide an upper bound on the integrality gap for a given vertex. This algorithm relies on dual formulations of related LP problems (DOPT+ and DOPTII) and a recursive construction to bound the gap of successors.
  • Computational Verification: The GB algorithm is applied to a set of ancestors for $k=3, 4, 5, 6$. To achieve the desired 4/3 bound, the authors also explore "successors" of these ancestors, guided by a heuristic that prioritizes BB-moves on edges with the largest associated constants. This computer-aided approach, implemented in Python with the Gurobi solver, allows them to verify the 4/3 conjecture for a large and previously unaddressed class of instances.

Datasets

Not discussed in the paper. The paper focuses on theoretical instances and computational verification rather than empirical datasets.

Key Insights and Ideas

  • The "n+6" Threshold: The paper's central insight is that if the optimal LP solution for an n-node TSP has at most n+6 non-zero components, the integrality gap is indeed 4/3. This provides a concrete and manageable condition for proving the conjecture for a large class of problems.
  • Ancestors and Successors: The introduction of "ancestors" as fundamental building blocks for families of vertices ($F_k$) simplifies the analysis. The concept of "successors" and the BB-move allows for a systematic exploration of related vertices, crucial for the computational verification.
  • Gap-Bounding Algorithm: The development of the GB algorithm is a significant methodological contribution. It provides a systematic way to bound the integrality gap by leveraging dual LP formulations and a recursive construction, making it adaptable to other problems.
  • Computational Proofs for Infinite Classes: The paper demonstrates the power of combining theoretical frameworks with computational methods to prove results for infinite families of instances, a departure from previous proofs that were often limited to fixed small numbers of nodes.
  • Few Edges Hypothesis: The paper's findings align with and support the "Few Edges Hypothesis," which suggests that the maximum integrality gap is achieved on vertices with the minimum possible number of edges in their support graph (n+3).

Key Results

  • The paper proves that the integrality gap of the symmetric metric Traveling Salesman Problem is 4/3 for all vertices of the subtour elimination polytope whose support graph contains at most $n+6$ edges.
  • This result is achieved through a novel methodology combining theoretical analysis (defining ancestors, families $F_k$, and the Gap-Bounding algorithm) and computational verification.
  • The computational results, summarized in Table 1, show that for $k=3, 4, 5, 6$, the upper bound on the integrality gap for the corresponding families of vertices is 4/3. The number of additional iterations required for the GB algorithm to achieve this bound is relatively small, indicating the efficiency of the approach.

Limitations and Future Work

  • Limited to n+6: While a significant step, the result is conditional on the number of non-zero components in the LP solution. The paper does not prove the 4/3 conjecture for all TSP instances.
  • Computational Cost for Larger k: The current approach relies on enumerating ancestors, which becomes computationally intensive for larger values of $k$. The paper mentions that constructing $A_7$ would be a natural next step.
  • Heuristic for Successor Selection: The choice of which successor to explore when an initial bound is not met is based on a heuristic (BB-move on the edge with the largest constant). While effective in this case, a more systematic approach might be beneficial.
  • Future Work: The authors suggest several avenues:
  • Extending the analysis to $k=7$ and beyond by enumerating $A_7$.
  • Investigating the correlation between the integrality gap and the number of edges in the support graph more deeply, potentially leading to a proof of the Few Edges Hypothesis.
  • Adapting the Gap-Bounding methodology to other combinatorial optimization problems.
  • Exploring the "donut instances" mentioned, which have high integrality gaps but do not fall into the families analyzed here.

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 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},
}

Loading related content...

Figure