The Optimality Program in Parameterized Algorithms

Parameterized complexity analyzes the computational complexity of
NP-hard combinatorial problems in finer detail than classical
complexity: instead of expressing the running time as a univariate
function of the size $n$ of the input, one or more relevant parameters
are defined and the running time is analyzed as a function depending
on both the input size and these parameters. The goal is to obtain
algorithms whose running time depends polynomially on the input size,
but may have arbitrary (possibly exponential) dependence on the
parameters. Moreover, we would like the dependence on the parameters
to be as slowly growing as possible, to make it more likely that the
algorithm is efficient in practice for small values of the
parameters. In recent years, advances in parameterized algorithms and
complexity have given us a tight understanding of how the parameter
has to influence the running time for various problems. The talk will
survey results of this form, showing that seemingly similar NP-hard
problems can behave in very different ways if they are analyzed in the
parameterized setting.