Kernelization Using Structural Parameters on Sparse Graph
Classes

D 2013

Kernelization Using Structural Parameters on Sparse Graph Classes

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL et. al.

Basic information

Original name

Kernelization Using Structural Parameters on Sparse Graph Classes

Authors

GAJARSKÝ, Jakub (703 Slovakia, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution), Sebastian ORDYNIAK (276 Germany, belonging to the institution), Felix REIDL (276 Germany), Peter ROSSMANITH (276 Germany), Fernando Sanchez VILLAAMIL (724 Spain) and Somnath SIKDAR (356 India)

Edition

Berlin Heidelberg, ESA 2013, p. 529-540, 12 pp. 2013

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/13:00066378

Organization unit

Faculty of Informatics

ISBN

978-3-642-40449-8

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-40450-4_45

UT WoS

000342754600045

Keywords in English

kernelization; parameterized complexity; sparse graphs

Abstract

V originále

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 these three 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. While our parameter may seem rather strong, a linear kernel result on graphs of bounded expansion with a weaker parameter would for some problems violate known lower bounds. Moreover, we use a relaxed notion of FII which allows us to prove linear kernels for problems such as Longest Path/Cycle and Exact s,t-Path which do not have FII in general graphs.

Links

EE2.3.30.0009, research and development project

Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

GAP202/11/0196, research and development project

Name: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů

Investor: Czech Science Foundation, Well-structured combinatorial classes, width parameters, and design of efficient algorithms

MUNI/A/0739/2012, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0760/2012, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)

Investor: Masaryk University, Category A

Citovat

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL, Peter ROSSMANITH, Fernando Sanchez VILLAAMIL and Somnath SIKDAR. Kernelization Using Structural Parameters on Sparse Graph Classes. In Hans L. Bodlaender a Giuseppe F. Italiano. ESA 2013. Berlin Heidelberg: Springer, 2013, p. 529-540. ISBN 978-3-642-40449-8. Available from: https://dx.doi.org/10.1007/978-3-642-40450-4_45.

@inproceedings{1123296,
   author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian and Reidl, Felix and Rossmanith, Peter and Villaamil, Fernando Sanchez and Sikdar, Somnath},
   address = {Berlin Heidelberg},
   booktitle = {ESA 2013},
   doi = {http://dx.doi.org/10.1007/978-3-642-40450-4_45},
   editor = {Hans L. Bodlaender a Giuseppe F. Italiano},
   keywords = {kernelization; parameterized complexity; sparse graphs},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin Heidelberg},
   isbn = {978-3-642-40449-8},
   pages = {529-540},
   publisher = {Springer},
   title = {Kernelization Using Structural Parameters on Sparse Graph Classes},
   year = {2013}
}

TY  - JOUR
ID  - 1123296
AU  - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian - Reidl, Felix - Rossmanith, Peter - Villaamil, Fernando Sanchez - Sikdar, Somnath
PY  - 2013
TI  - Kernelization Using Structural Parameters on Sparse Graph Classes
PB  - Springer
CY  - Berlin Heidelberg
SN  - 9783642404498
KW  - kernelization
KW  - parameterized complexity
KW  - sparse graphs
N2  - 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 these three 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. While our parameter may seem rather strong, a linear kernel result on graphs of bounded expansion with a weaker parameter would for some problems violate known lower bounds. Moreover, we use a relaxed notion of FII which allows us to prove linear kernels for problems such as Longest Path/Cycle and Exact s,t-Path which do not have FII in general graphs.
ER  -

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Sebastian ORDYNIAK, Felix REIDL, Peter ROSSMANITH, Fernando Sanchez VILLAAMIL and Somnath SIKDAR. Kernelization Using Structural Parameters on Sparse Graph Classes. In Hans L. Bodlaender a Giuseppe F. Italiano. \textit{ESA 2013}. Berlin Heidelberg: Springer, 2013, p.~529-540. ISBN~978-3-642-40449-8. Available from: https://dx.doi.org/10.1007/978-3-642-40450-4\_{}45.

Detailed Information on Publication Record