Kernelization using structural parameters on sparse graph classes

摘要: We prove that graph problems with finite integer index have linear kernels on graphs of bounded expansion when parameterized by the size a modulator to constant-treedepth graphs. For nowhere dense classes, our result yields almost-linear kernels. also argue such kernelization weaker parameter would fail include some covered framework. only require FII constant treedepth. This allows for as Longest-Path/Cycle, Exact- s , t -Path, Treewidth, and Pathwidth, which do not general Meta-theorems been subject intensive research.We follow line toward even larger classes using stronger parametrization.FII expansion, treedepth-modulator.For this kernels.FII is required