The \(k\)-opt algorithm is one of the simplest and most widely used heuristics for solving the traveling salesman problem. Starting from an arbitrary tour, the \(k\)-opt algorithm improves the current tour in each iteration by exchanging up to \(k\) edges. The algorithm continues until no further improvement of this kind is possible. For a long time, it remained an open question how many iterations the \(k\)-opt algorithm might require for small values of \(k\), assuming the use of an optimal pivot rule. In this paper, we resolve this question for the cases \(k = 3\) and \(k = 4\) by proving that in both these cases an exponential number of iterations may be needed even if an optimal pivot rule is used. Combined with a recent result by Heimann, Hoang, and Hougardy (ICALP 2024), this provides a complete answer for all \(k \ge 3\) regarding the number of iterations the \(k\)-opt algorithm may require under an optimal pivot rule. In addition we establish an analogous exponential lower bound for the 2.5-opt algorithm, a variant that generalizes 2-opt and is a restricted version of 3-opt. All our results hold for both the general and the metric traveling salesman problem.

The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most $k$ edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the $k$-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We show the two properties above for a much smaller value of $k$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for $k \geq 17$ and the exponential running time for $k \geq 5$.