2017/06/28 by Eduard Eiben, Eiben, Eduard, Mithilesh Kumar +7 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1706.09339
arxiv created 2018/02/22 · arxiv updated 2018/02/23
For α> 1, an α-approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem 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⋅α)-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 α>1, Connected Dominating Set admits a polynomial-size α-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 \textsfNP ⊆ \textsfcoNP/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∈ℕ there cannot exist an α-approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on C for any α>1 (assuming the Gap Exponential Time Hypothesis).