The Parameterized Complexity of Local Search for TSP, More Refined

• DOI: 10.1007/s00453-012-9685-8
• Publication Date: 2012-09-07T16:31:31Z
• Authors: Jiong Guo; Sepp Hartung; Rolf Niedermeier; Ondřej Suchý
• Keywords: Theory of computation; Exponential time hypothesis; Hardness of approximation

We extend previous work on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (which define the local search area) "Edge Exchange" and "Max-Shift". We perform studies with respect to the distance measures "Swap" and "m-Swap", "Reversal" and "m-Reversal", and "Edit", achieving both fixed-parameter tractability and W[1]-hardness results. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.