The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints

The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder, what is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation. Funding: The research of E. Vercesi was supported by the Swiss National Science Foundation [Grant 200021_212929/1] “Computational methods for integrality gaps analysis.” The research of A. Buchanan is based on work supported by the National Science Foundation [Grant 1942065] and the Air Force Office of Scientific Research [Grant FA9550-25-1-0277]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0078 .