Kernelization using structural parameters on sparse graph
classes

J 2017

Kernelization using structural parameters on sparse graph classes

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

Základní údaje

Originální název

Kernelization using structural parameters on sparse graph classes

Autoři

GAJARSKÝ, Jakub; Petr HLINĚNÝ ; Jan OBDRŽÁLEK; Sebastian ORDYNIAK; Felix REIDL; Peter ROSSMANITH; Fernando VILLAAMIL a Somnath SIKDAR

Vydání

Journal of Computer and System Sciences, SAN DIEGO, Elsevier, 2017, 0022-0000

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Impakt faktor

Impact factor: 1.497

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/17:00094632

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Parameterized complexity; Kernelization; Nowhere dense graphs; Finite integer index; Treedepth

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2018 10:06, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We prove that graph problems with finite integer index 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. We also argue that such a linear kernelization result with a weaker parameter would fail to include some of the problems covered by our framework. We only require the problems to have FII on graphs of constant treedepth. This allows to prove linear kernels also for problems such as Longest-Path/Cycle, Exact-s, t-Path, Treewidth, and Pathwidth, which do not have FII on general graphs. (C) 2016 Elsevier Inc. All rights reserved.

Návaznosti

GA14-03501S, projekt VaV

Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

MUNI/A/0945/2015, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

GAJARSKÝ, Jakub; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Sebastian ORDYNIAK; Felix REIDL; Peter ROSSMANITH; Fernando VILLAAMIL a Somnath SIKDAR. Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences. SAN DIEGO: Elsevier, 2017, roč. 84, č. 1, s. 219-242. ISSN 0022-0000. Dostupné z: https://doi.org/10.1016/j.jcss.2016.09.002.

@article{1372352,
   author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian and Reidl, Felix and Rossmanith, Peter and Villaamil, Fernando and Sikdar, Somnath},
   article_location = {SAN DIEGO},
   article_number = {1},
   doi = {https://doi.org/10.1016/j.jcss.2016.09.002},
   keywords = {Parameterized complexity; Kernelization; Nowhere dense graphs; Finite integer index; Treedepth},
   language = {eng},
   issn = {0022-0000},
   journal = {Journal of Computer and System Sciences},
   title = {Kernelization using structural parameters on sparse graph classes},
   volume = {84},
   year = {2017}
}

TY  - JOUR
ID  - 1372352
AU  - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian - Reidl, Felix - Rossmanith, Peter - Villaamil, Fernando - Sikdar, Somnath
PY  - 2017
TI  - Kernelization using structural parameters on sparse graph classes
JF  - Journal of Computer and System Sciences
VL  - 84
IS  - 1
SP  - 219-242
EP  - 219-242
PB  - Elsevier
SN  - 00220000
KW  - Parameterized complexity
KW  - Kernelization
KW  - Nowhere dense graphs
KW  - Finite integer index
KW  - Treedepth
N2  - We prove that graph problems with finite integer index 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. We also argue that such a linear kernelization result with a weaker parameter would fail to include some of the problems covered by our framework. We only require the problems to have FII on graphs of constant treedepth. This allows to prove linear kernels also for problems such as Longest-Path/Cycle, Exact-s, t-Path, Treewidth, and Pathwidth, which do not have FII on general graphs. (C) 2016 Elsevier Inc. All rights reserved.
ER  -

GAJARSKÝ, Jakub; Petr HLINĚNÝ; Jan OBDRŽÁLEK; Sebastian ORDYNIAK; Felix REIDL; Peter ROSSMANITH; Fernando VILLAAMIL a Somnath SIKDAR. Kernelization using structural parameters on sparse graph classes. \textit{Journal of Computer and System Sciences}. SAN DIEGO: Elsevier, 2017, roč.~84, č.~1, s.~219-242. ISSN~0022-0000. Dostupné z: https://doi.org/10.1016/j.jcss.2016.09.002.

Přehled o publikaci