Kernelization Using Structural Parameters on Sparse Graph Classes

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Kernelization Using Structural Parameters on Sparse Graph Classes

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Kernelization Using Structural Parameters on Sparse Graph Classes

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název statě ve sborníku

ESA 2013

ISBN

9783642404498

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

529-540

Název nakladatele

Springer

Místo vydání

Berlin Heidelberg

Místo konání akce

Sophia Antipolis, France

Datum konání akce

1. 1. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—