Department of
Applied
Mathematics

The Parameterized Complexity of Local Search for TSP

Ondra Suchý

University of Saarland

Abstract

We give more refined view on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP), extending previous work. 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 will mention non-existence results for polynomial-size problem kernels and we will show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.

This is joint work with Jiong Guo, Sepp Hartung, and Rolf Niedermeier.