Working Seminar on Formal Models, Discrete Structures, and Algorithms

Kernelization and Sparse Graph Classes

Felix Reidl (RWTH Aachen University)

When: November 12, 2pm

Where: room G2.91b


In the field of parameterized complexity, problems are analyzed under a secondary measure called the parameter. Those problems, for which an algorithm exists which takes time polynomial in the input length but an arbitrary function of this parameter, are classified as fixed parameter tractable.

An interesting characterization of fixed-parameter tractable problems is that there exists a polynomial-time data reduction algorithm that ``compresses'' an instance of the problem into an equivalent instance–called a problem kernel–whose size is bounded by some function of the parameter.

Of particular interest is the subclass of fixed parameter problems which admit kernels of polynomial size. In the course of the last decade, many such problem kernels where found if one restricts the input to sparse classes of graphs: these results where unified and generalized by so-called meta-kernelizations. We present an overview over these techniques and discuss possible directions for further research.