Meta-kernelization using well-structured modulators

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106819" target="_blank" >RIV/00216224:14330/18:00106819 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.dam.2017.09.018" target="_blank" >http://dx.doi.org/10.1016/j.dam.2017.09.018</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2017.09.018" target="_blank" >10.1016/j.dam.2017.09.018</a>

Result language

angličtina

Original language name

Meta-kernelization using well-structured modulators

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Volume of the periodical

248

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

153-167

UT code for WoS article

000447109400015

EID of the result in the Scopus database

2-s2.0-85033494153