Kernelization Using Structural Parameters on Sparse Graph Classes

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

Základní údaje

Originální název

Kernelization Using Structural Parameters on Sparse Graph Classes

Autoři

GAJARSKÝ, Jakub (703 Slovensko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Jan OBDRŽÁLEK (203 Česká republika, domácí), Sebastian ORDYNIAK (276 Německo, domácí), Felix REIDL (276 Německo), Peter ROSSMANITH (276 Německo), Fernando Sanchez VILLAAMIL (724 Španělsko) a Somnath SIKDAR (356 Indie)

Vydání

Berlin Heidelberg, ESA 2013, od s. 529-540, 12 s. 2013

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/13:00066378

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-40449-8

ISSN

DOI

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

UT WoS

000342754600045

Klíčová slova anglicky

kernelization; parameterized complexity; sparse graphs

Štítky

core_A, firank_A, formela-conference, kernelization, parameterized complexity

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

---

Návaznosti

EE2.3.30.0009, projekt VaV	Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
GAP202/11/0196, projekt VaV	Název: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů Investor: Grantová agentura ČR, Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
MUNI/A/0739/2012, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU) Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0760/2012, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty