Meta-kernelization with structural parameters
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Meta-kernelization with structural parameters
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Computer and System Sciences
ISSN
0022-0000
e-ISSN
—
Volume of the periodical
82
Issue of the periodical within the volume
2
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
14
Pages from-to
333-346
UT code for WoS article
000366240700009
EID of the result in the Scopus database
2-s2.0-84955656358