The most successful approaches for the 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 handful of SECs are imposed? Also, for a given instance, what is the minimum number of SECs needed to prove optimality? 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. 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.

## Citation

Submitted to a journal

## Article

View The Dantzig-Fulkerson-Johnson TSP formulation is easy to solve for few subtour constraints