Lower bounds on kernelization

Preprocessing (data reduction or kernelization) to reduce instance size is one of the most commonly deployed heuristics in the implementation practice to tackle computationally hard problems. However, a systematic theoretical study of them has remained elusive so far. One of the reasons for this is that if an input to an NP-hard problem can be processed in polynomial time to an equivalent one of smaller size in general, then the preprocessing algorithm can be used to actually solve   the problem in polynomial time proving P=NP, which is expected to be unlikely. However the situation regarding systematic study changed drastically with the advent of parameterized complexity. Parameterized complexity provides a natural framework to analyse preprocessing algorithms. In a parameterized problem, every instance xx comes with a positive integer, or parameter, kk. The problem is said to admit a kernel if, in polynomial time, we can reduce the size of the instance xx to a function in kk, while preserving the answer.The central notion in parameterized complexity is fixed parameter tractability (FPT)  , which is the notion of solvability in f(k)⋅p(|x|)f(k)⋅p(|x|) time for any given instance (x,k)(x,k), where ff is an arbitrary function of the parameter kk and pp is a polynomial in the input size |x||x|. It is widely believed that a parameterized problem ΠΠ is fixed-parameter tractable if and only if there exists a computable function g(k)g(k) such that ΠΠ admits a kernel of size g(k)g(k). However, the kernels obtained by this theoretical result are usually of exponential (or even worse) sizes, while problem-specific data reductions often achieve quadratic- or even linear-size kernels. So a natural question for any concrete FPT problem is whether it admits polynomial time kernelization to a problem kernel that in the worst case is bounded by a polynomial function of the parameter. Despite several attempts, there are fixed-parameter tractable problems that have only exponential sized kernels. An explanation was provided in a paper by Bodlaender et al. (2009) [8], where it was shown that unless coNP⊆NP/poly, there are fixed-parameter tractable problems that cannot have a polynomial sized kernel. This triggered further work on showing lower bounds of kernels, and this article surveys recent developments in the area, starting from the framework developed in the paper by Bodlaender et al. (2009) [8].