Kernelization Using Structural Parameters on Sparse Graph Classes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00066378" target="_blank" >RIV/00216224:14330/13:00066378 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-40450-4_45" target="_blank" >http://dx.doi.org/10.1007/978-3-642-40450-4_45</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-40450-4_45" target="_blank" >10.1007/978-3-642-40450-4_45</a>

Result language
angličtina
Original language name
Kernelization Using Structural Parameters on Sparse Graph Classes
Original language description
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, there were meta-theorems for linear kernels on graphs of bounded genus, H-minor-free graphs, and H-topological-minor-free graphs. To the best of our knowledge, there are no known meta-theorems for kernels for any of the larger sparse graph classes: graphs of bounded expansion, locally bounded expansion, and nowhere dense graphs. In this paper we prove meta-theorems for thesethree graph classes. More specifically, we show that graph problems that have finite integer index (FII) admit linear kernels on hereditary graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For hereditary graph classes of locally bounded expansion, our result yields a quadratic kernel and for hereditary nowhere dense graphs, a polynomial kernel.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)