Felix Reidl: Meta-kernelization and sparsity

The Meta-kernelization paper by Bodlaender et al. (2009) was a breakthrough of in the quest for polynomial kernels on problems on graphs of bounded genus (which include planar graphs). We managed to lift up this results to classes that exclude a topological minor (Kim et al., 2012) and finally bounded expansion and nowhere dense classes (Gajarský et al., 2013), both times having to re-think the previous results in order to make headway.

I will talk about the meta-kernelization toolkit and how our understanding of the original result has changed through lifting it up along the sparse graph hierarchy.