Eiben, Eduard ;
Ganian, Robert ;
Szeider, Stefan
Metakernelization using Wellstructured Modulators
Abstract
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 metakernelization 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 rankwidth and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulatorsize to more general parameters, hence providing smaller kernels. We show (i) how such large but wellstructured modulators can be efficiently approximated, (ii) how they can be used to obtain polynomial kernels for any graph problem expressible in Monadic Second Order logic, and (iii) how they allow the extension of previous results in the area of structural metakernelization.
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2015:5576,
author = {Eduard Eiben and Robert Ganian and Stefan Szeider},
title = {{Metakernelization using Wellstructured Modulators}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {114126},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5576},
URN = {urn:nbn:de:0030drops55769},
doi = {10.4230/LIPIcs.IPEC.2015.114},
annote = {Keywords: Kernelization, Parameterized complexity, Structural parameters, Rankwidth, Split decompositions}
}
2015
Keywords: 

Kernelization, Parameterized complexity, Structural parameters, Rankwidth, Split decompositions 
Seminar: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Issue date: 

2015 
Date of publication: 

2015 