Kernelization via magic

A polynomial kernel, for a parameterized problem with parameter k, is a polynomial-time reduction which reduces an instance to total size poly(k), while maintaining the solution status. For example, the classical Nemhauser/Trotter result for Vertex Cover implies a polynomial-time reduction to an instance with 2*OPT vertices, while preserving the size of an optimal solution (note that this is stronger than just a 2-approximation). The existence of a polynomial kernel is a fundamental property of parameterized problems.

Recently, significant advancements in kernelization have been made with the introduction of tools from matroid theory, in particular, a lemma on <i>representative sets</i> due to Marx and Lov&aacute;sz.

In this talk, I give a brief presentation of this result, and sketch its applications to kernelization, including several "first" polynomial kernels and a form of cut-covering sets.