Title: Improving TSP tours using dynamic programming over tree decomposition,
Abstract: Given a traveling salesman problem (TSP) tour $H$ in graph $G$ a $k$-move is
an operation which removes $k$ edges from $H$, and adds $k$ edges of $G$ so
that a new tour $H'$ is formed. The popular $k$-OPT heuristics 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(n^k)$. At ICALP'16 de Berg,
Buchin, Jansen and Woeginger showed an $O(n^{\lfloor 2/3k \rfloor+1})$-time
algorithm.
We show an algorithm which runs in $O(n^{(1/4+\epsilon_k)k})$ time, where
$\lim \epsilon_k = 0$. We are able to show that it improves over the state of
the art for every $k=5,\ldots,10$. For the most practically relevant case $k=5$
we provide a slightly refined algorithm running in $O(n^{3.4})$ time. We also
show that for the $k=4$ case, improving over the $O(n^3)$-time algorithm of de
Berg et al. would be a major breakthrough: an $O(n^{3-\epsilon})$-time
algorithm for any $\epsilon>0$ would imply an $O(n^{3-\delta})$-time algorithm
for the ALL PAIRS SHORTEST PATHS problem, for some $\delta>0$.