Improving TSP Tours Using Dynamic Programming over Tree Decompositions

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation that removes k edges from H and adds k edges of G so that a new tour H′ is formed. The popular k-OPT heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(nk). At ICALP’16, de Berg, Buchin, Jansen, and Woeginger showed an O(n⌊2k/3⌋+1)-time algorithm. We show an algorithm that runs in O(n(1/4+ek)k) time, where limk→ ∞ ek e 0. It improves over the state of the art for every k ≥ 5. For the most practically relevant case k e 5, we provide a slightly refined algorithm running in O(n3.4) time. We also show that for the k e 4 case, improving over the O(n3)-time algorithm of de Berg et al. would be a major breakthrough: An O(n3−e)-time algorithm for any e > 0 would imply an O(n3−δ)-time algorithm for the All Pairs Shortest Paths problem, for some δ > 0.