Authors: Jiong Guo Sepp Hartung Rolf Niedermeier Ondřej Suchý
Publish Date: 2012/09/08
Volume: 67, Issue: 1, Pages: 89-110
Abstract
We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem TSP So far its parameterized complexity has been investigated with respect to the distance measures defining the local search area “Edge Exchange” and “MaxShift” We perform studies with respect to the distance measures “Swap” and “rSwap” “Reversal” and “rReversal” and “Edit” achieving both fixedparameter tractability and W1hardness results In particular from the parameterized reduction showing W1hardness we infer running time lower bounds based on the exponential time hypothesis for all corresponding distance measures Moreover we provide nonexistence results for polynomialsize problem kernels and we show that some in general W1hard problems turn fixedparameter tractable when restricted to planar graphsAn extended abstract of this paper appeared in Proceedings of the 22nd International Symposium on Algorithms and Computation ISAAC’11 Yokohama Japan Dec 2011 volume 7074 of LNCS pages 614–623 Springer 2011 An important difference compared to the conference version is that we significantly improved the running time lower bounds
Keywords: