License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.29
URN: urn:nbn:de:0030-drops-85027
URL: http://drops.dagstuhl.de/opus/volltexte/2018/8502/
Go to the corresponding LIPIcs Volume Portal


Eiben, Eduard ; Kumar, Mithilesh ; Mouawad, Amer E. ; Panolan, Fahad ; Siebertz, Sebastian

Lossy Kernels for Connected Dominating Set on Sparse Graphs

pdf-format:
LIPIcs-STACS-2018-29.pdf (0.5 MB)


Abstract

For alpha > 1, an alpha-approximate (bi-)kernel for a problem Q is a polynomial-time 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 c-approximate 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 distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every alpha > 1, Connected Dominating Set admits a polynomial-size alpha-approximate (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 2-degenerate 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 alpha-approximate bi-kernel for the (Connected) Distance-r 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:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8502},
  URN =		{urn:nbn:de:0030-drops-85027},
  doi =		{10.4230/LIPIcs.STACS.2018.29},
  annote =	{Keywords: Lossy Kernelization, Connected Dominating Set, Sparse Graph Classes}
}

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: 20.02.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI