Details

Autor(en) / Beteiligte

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

Titel

Kernelization using structural parameters on sparse graph classes

Ist Teil von

• Journal of computer and system sciences, 2017-03, Vol.84, p.219-242

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

2017

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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. •Meta-theorems for linear kernels have been the subject of intensive research.•We follow the line toward even larger graph classes using stronger parametrization.•FII problems have linear kernels on graphs of bounded expansion, parameterized by the size of a treedepth-modulator.•For nowhere dense classes, this yields almost-linear kernels.•FII is required only on graphs of bounded treedepth.