Kernelization Using Structural Parameters on Sparse Graph Classes
| Autor: | Gajarský, Jakub, Hliněný, Petr, Obdržálek, Jan, Ordyniak, Sebastian, Reidl, Felix, Rossmanith, Peter, Villaamil, Fernando Sánchez, Sikdar, Somnath |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, $H$-minor-free graphs, and $H$-topological-minor-free graphs. To the best of our knowledge, no meta-theorems for polynomial kernels are known for any larger sparse graph classes; e.g., for classes of bounded expansion or for nowhere dense ones. In this paper we prove such meta-theorems for the two latter cases. More specifically, we show that graph problems that have finite integer index (FII) 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. While our parameter may seem rather strong, we argue that a linear kernelization result on graphs of bounded expansion with a weaker parameter (than treedepth modulator) would fail to include some of the problems covered by our framework. Moreover, we only require the problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact $s,t$-Path, Treewidth, and Pathwidth, which do not have FII on general graphs (and the first two not even on bounded treewidth graphs). Comment: A preliminary version appeared as an extended abstract in the proceedings of ESA 2013, and one section in the proceedings of IPEC 2014. Changes from the previous version: inclusion of the IPEC 2014 results; much stronger conclusion for the case of nowhere dense graph classes; inclusion of some additional problems in the framework, e.g., of the branchwidth problem |
| Databáze: | arXiv |
| Externí odkaz: |
|