Portal de Periódicos da CAPES

Kernelization using structural parameters on sparse graph classes

2016; Elsevier BV; Volume: 84; Linguagem: Inglês

10.1016/j.jcss.2016.09.002

1090-2724

Jakub Gajarský, Petr Hliněný, Jan Óbdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar,

Interconnection Networks and Systems

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.