Meta-kernelization with structural parameters

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00100544" target="_blank" >RIV/00216224:14330/16:00100544 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Meta-kernelization with structural parameters

Popis výsledku v původním jazyce

Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the -cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to . We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the -cover number. We provide similar results for MSO expressible optimization and modulo-counting problems.

Název v anglickém jazyce

Meta-kernelization with structural parameters

Popis výsledku anglicky

Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the -cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to . We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the -cover number. We provide similar results for MSO expressible optimization and modulo-counting problems.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

82

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

333-346

Kód UT WoS článku

000366240700009

EID výsledku v databázi Scopus

2-s2.0-84955656358