Header menu link for other important links
X
Lossy kernels for connected dominating set on sparse graphs
E. Eiben, M. Kumar, A.E. Mouawad, , S. Siebertz
Published in Society for Industrial and Applied Mathematics Publications
2019
Volume: 33
   
Issue: 3
Pages: 1743 - 1771
Abstract
For \alpha > 1, an \alpha -approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem \scrQ and outputs an instance (I\prime , k\prime ) (of a problem \scrQ \prime ) of size bounded by a function of k such that, for every c \geq 1, a c-approximate solution for the new instance can be turned into a (c \cdot \alpha )-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. 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 \scrC is somewhere dense and closed under taking subgraphs, then for some value of r \in \BbbN there cannot exist an \alpha -approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on \scrC for any \alpha > 1 (assuming FPT \not = W[1]). ©2019 Society for Industrial and Applied Mathematics
About the journal
JournalSIAM Journal on Discrete Mathematics
PublisherSociety for Industrial and Applied Mathematics Publications
ISSN08954801