Eiben, Eduard ;
Kumar, Mithilesh ;
Mouawad, Amer E. ;
Panolan, Fahad ;
Siebertz, Sebastian
Lossy Kernels for Connected Dominating Set on Sparse Graphs
Abstract
For alpha > 1, an alphaapproximate (bi)kernel for a problem Q is a polynomialtime algorithm that takes as input an instance (I, k) of Q and outputs an instance (I',k') (of a problem Q') of size bounded by a function of k such that, for every c >= 1, a capproximate solution for the new instance can be turned into a (c alpha)approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distancer variant) parameterized by solution size on sparse graph classes like bicliquefree graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every alpha > 1, Connected Dominating Set admits a polynomialsize alphaapproximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r \in N there cannot exist an alphaapproximate bikernel for the (Connected) Distancer Dominating Set problem on C for any alpha > 1 (assuming the Gap Exponential Time Hypothesis).
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2018:8502,
author = {Eduard Eiben and Mithilesh Kumar and Amer E. Mouawad and Fahad Panolan and Sebastian Siebertz},
title = {{Lossy Kernels for Connected Dominating Set on Sparse Graphs}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {29:129:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8502},
URN = {urn:nbn:de:0030drops85027},
doi = {10.4230/LIPIcs.STACS.2018.29},
annote = {Keywords: Lossy Kernelization, Connected Dominating Set, Sparse Graph Classes}
}
27.02.2018
Keywords: 

Lossy Kernelization, Connected Dominating Set, Sparse Graph Classes 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 