Title: Lower Bounds for Kernelization
Abstract:
Kernelization is the process of transforming the input of
a combinatorial problem to an equivalent input whose size
is bounded by a function of the parameter; the analysis of
kernelization tells what we can achieve with polynomial
time preprocessing for combinatorial problems, and is a
recent active field in algorithm research. In this talk,
a survey is given of a number of recent techniques to show
(under complexity theoretic assumptions) lower bounds for
the size of kernels. In particular, it is discussed how
the notion of compositionality can show that certain
(parameterized) problems do not have kernels of polynomial
size.