Improving TSP tours using dynamic programming over tree decomposition

Marek Cygan, Lukasz Kowalik, Arkadiusz Socala

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^{\prime }$ is for…