Kernelization of Generic Problems: Upper and Lower Bounds

problems, defined via syntactical restrictions or by a problem
framework. Polynomial kernelization formalizes data reduction,
which allows a rigorous study of this important and fundamental
concept.

In the first part of the thesis we prove that all problems from two
syntactically defined classes of constant-factor approximable
problems admit polynomial kernelizations. Next, we consider
edge modification problems, and we show that they do not generally
admit polynomial kernelizations.

In the second part we consider three types of Boolean constraint
satisfaction problems. We completely characterize whether these
problems admit polynomial kernelizations depending on properties of
the permitted constraints.