On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
This resolves an open question in computational complexity theory, providing a tighter bound for the hardness of local search in combinatorial optimization.
The paper tackled the problem of proving PLS-completeness for the $k$-Opt local search algorithm in the traveling salesman problem, achieving a rigorous proof and reducing the required $k$ from over 1000 to $k \\geq 15$.
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). However, his proof requires $k \gg 1000$ and has a substantial gap. We provide the first rigorous proof for the PLS-completeness and at the same time drastically lower the value of $k$ to $k \geq 15$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). Our result holds for both the general and the metric traveling salesman problem.