[Back]

J. Gajarsky, P. Hlinený, J. Obdrzalek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Villaamil Sanchez, S. Sikdar:
"Kernelization using structural parameters on sparse graph classes";
Journal of Computer and System Sciences, 84 (2017), 219 - 242.

We prove that graph problems with finite integer index have linear kernels
on graphs of bounded expansion when parameterized by the size of a modulator
to constant-treedepth graphs. For nowhere dense graph classes, our result
yields almost-linear kernels. We also argue that such a linear kernelization
result with a weaker parameter would fail to include some of the problems
covered by our framework. We only require the problems to have FII on graphs
of constant treedepth. This allows to prove linear kernels also for problems
such as Longest-Path/Cycle, Exact-s,t-Path, Treewidth, and Pathwidth, which
do not have FII on general graphs.

http://dx.doi.org/10.1016/j.jcss.2016.09.002

http://www.sciencedirect.com/science/article/pii/S0022000016300812?via%3Dihub