{"id":"arxiv/2603.11270","url":"https://arxiv.org/abs/2603.11270","tags":["cs.DS","math.CO"],"score":0,"title":"On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem","domain":"cs.DS","source":"arxiv","authors":["Sophia Heimann","Hung P. Hoang","Stefan Hougardy"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-11","reactions":{}}