2026-08-17T21:08:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8502 2024-03-06T10:42:19Z ddc:004 open_access

Lossy Kernels for Connected Dominating Set on Sparse Graphs Eiben, Eduard Kumar, Mithilesh Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian Lossy Kernelization Connected Dominating Set Sparse Graph Classes 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Mithilesh Kumar and Amer E. Mouawad and Fahad Panolan and Sebastian Siebertz 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.29 urn:nbn:de:0030-drops-85027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.29 eng https://creativecommons.org/licenses/by/3.0/legalcode