Polynomial Kernels for Graph and Hypergraph Optimisation Problems

When dealing with hard problems, problems which we are not able to solve in polynomial time, it is common practice to preprocess an instance to reduce its size and make the task of solving it easier. Parameterized Complexity offers a theoretical framework to prove the efficiency of preprocessing algorithms, which are called kernelizations. The underlying idea is that for every problem we identify a parameter which represents the part of the input which is 'difficult' to solve, then we try to reduce the input size and we measure the result in terms of the parameter.

Especially successful kernelizations are the ones that compute a kernel whose size is bounded by a polynomial in the parameter. In this thesis we consider some combinatorial optimisation problems on graphs and hypergraphs, and we study the existence (or non-existence) of polynomial kernels for these problems. In particular, we describe a generic kernelization for a theoretical class of graph problems, which can be used to derive the existence of a polynomial kernel for many graph problems of interest.