Kernelization for a Hierarchy of Structural Parameters

ABSTRACT

There are various reasons to study the kernelization complexity of non-standard parameterizations. Problems such as Chromatic Number are NP-complete for a constant value of the natural parameter, hence we should not hope to obtain kernels for this parameter. For other problems such as Long Path, the natural parameterization is fixed-parameter tractable but is known not to admit a polynomial kernel unless the polynomial hierarchy collapses. We may therefore guide the search for meaningful preprocessing rules for these problems by studying the existence of polynomial kernels for different parameterizations.

Another motivation is formed by the Vertex Cover problem. Its natural parameterization admits a small kernel, but there exist refined parameters (such as the feedback vertex number) which are structually smaller than the natural parameter, for which polynomial kernels still exist; hence we may obtain better preprocessing studying the properties of such refined parameters.

In this survey talk we discuss recent results on the kernelization complexity of structural parameterizations of these important graph problems. We consider a hierarchy of structural graph parameters, and try to pinpoint the best parameters for which polynomial kernels still exist.

Given at WorKer 2011 – The Third Workshop on Kernelization (slides are linked there).