Abstrakt
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms.
Parameterized complexity offers a framework to design algorithms exploiting such a structure and also means to analyze how well particular algorithms scale as the input structure becomes more and more complex.
In this talk we survey some parameterized algorithms for the Traveling Salesperson Problem and its generalizations.
We start with results concerning local search, where the parameter is the size of the solution neighborhood to be searched.
Then we move on to the so called 'structural parameters' which measure the complexity of the structure of the input graph.
The most prominent of such measures is the treewidth.
Finally, if time permits, we focus on the kernelization results for the problem.
Kernelization is a notion capturing efficient polynomial time data reductions, within the parameterized setting.
Here, we present our recent results, e.g., a polynomial-size kernel with respect to feedbeck edge number or vertex cover number.
The talk is based on a joint work with Václav Blažej, Pratibha Choudhary, Jiong Guo, Sepp Hartung, Dušan Knop, Rolf Niedermeier, Šimon Schierreich, and Tomáš Valla