Meta-kernelization using well-structured modulators

J 2018

Meta-kernelization using well-structured modulators

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER

Základní údaje

Originální název

Meta-kernelization using well-structured modulators

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí) a Stefan SZEIDER (40 Rakousko)

Vydání

Discrete Applied Mathematics, Elsevier Science, 2018, 0166-218X

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

Kód RIV

RIV/00216224:14330/18:00106819

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.dam.2017.09.018

UT WoS

000447109400015

Klíčová slova anglicky

kernelization; modulators; parameterized complexity

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 3. 5. 2019 14:59, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Kernelization investigates exact preprocessing algorithms with performance guarantees. The most prevalent type of parameters used in kernelization is the solution size for optimization problems; however, also structural parameters have been successfully used to obtain polynomial kernels for a wide range of problems. Many of these parameters can be defined as the size of a smallest modulator of the given graph into a fixed graph class (i.e., a set of vertices whose deletion puts the graph into the graph class). Such parameters admit the construction of polynomial kernels even when the solution size is large or not applicable. This work follows up on the research on meta-kernelization frameworks in terms of structural parameters. We develop a class of parameters which are based on a more general view on modulators: instead of size, the parameters employ a combination of rank-width and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulator-size to more general parameters, hence providing small kernels even in cases where previously developed approaches could not be applied. We show (i) how such large but well-structured modulators can be efficiently approximated, (ii) how they can be used to obtain polynomial kernels for graph problems expressible in Monadic Second Order logic, and (iii) how they support the extension of previous results in the area of structural meta-kernelization.

Návaznosti

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

Citovat

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER. Meta-kernelization using well-structured modulators. Discrete Applied Mathematics. Elsevier Science, 2018, roč. 248, č. 1, s. 153-167. ISSN 0166-218X. Dostupné z: https://dx.doi.org/10.1016/j.dam.2017.09.018.

@article{1523840,
   author = {Eiben, Eduard and Ganian, Robert and Szeider, Stefan},
   article_number = {1},
   doi = {http://dx.doi.org/10.1016/j.dam.2017.09.018},
   keywords = {kernelization; modulators; parameterized complexity},
   language = {eng},
   issn = {0166-218X},
   journal = {Discrete Applied Mathematics},
   title = {Meta-kernelization using well-structured modulators},
   volume = {248},
   year = {2018}
}

TY  - JOUR
ID  - 1523840
AU  - Eiben, Eduard - Ganian, Robert - Szeider, Stefan
PY  - 2018
TI  - Meta-kernelization using well-structured modulators
JF  - Discrete Applied Mathematics
VL  - 248
IS  - 1
SP  - 153-167
EP  - 153-167
PB  - Elsevier Science
SN  - 0166218X
KW  - kernelization
KW  - modulators
KW  - parameterized complexity
N2  - Kernelization investigates exact preprocessing algorithms with performance guarantees. The most prevalent type of parameters used in kernelization is the solution size for optimization problems; however, also structural parameters have been successfully used to obtain polynomial kernels for a wide range of problems. Many of these parameters can be defined as the size of a smallest modulator of the given graph into a fixed graph class (i.e., a set of vertices whose deletion puts the graph into the graph class). Such parameters admit the construction of polynomial kernels even when the solution size is large or not applicable. This work follows up on the research on meta-kernelization frameworks in terms of structural parameters. We develop a class of parameters which are based on a more general view on modulators: instead of size, the parameters employ a combination of rank-width and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulator-size to more general parameters, hence providing small kernels even in cases where previously developed approaches could not be applied. We show (i) how such large but well-structured modulators can be efficiently approximated, (ii) how they can be used to obtain polynomial kernels for graph problems expressible in Monadic Second Order logic, and (iii) how they support the extension of previous results in the area of structural meta-kernelization.
ER  -

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER. Meta-kernelization using well-structured modulators. \textit{Discrete Applied Mathematics}. Elsevier Science, 2018, roč.~248, č.~1, s.~153-167. ISSN~0166-218X. Dostupné z: https://dx.doi.org/10.1016/j.dam.2017.09.018.

Podrobný výpis o publikaci