Lower bounds on kernelization

Abstract

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 x comes with a positive integer, or parameter, k. The problem is said to admit a kernel if, in polynomial time, we can reduce the size of the instance x to a function in k, while preserving the answer.