Kernelization using structural parameters on sparse graph classes

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	GAJARSKÝ Jakub HLINĚNÝ Petr OBDRŽÁLEK Jan ORDYNIAK Sebastian REIDL Felix ROSSMANITH Peter VILLAAMIL Fernando SIKDAR Somnath
Rok publikování	2017
Druh	Článek v odborném periodiku
Časopis / Zdroj	Journal of Computer and System Sciences
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	http://dx.doi.org/10.1016/j.jcss.2016.09.002
Obor	Informatika
Klíčová slova	Parameterized complexity; Kernelization; Nowhere dense graphs; Finite integer index; Treedepth
Popis	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.
Související projekty:	Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.