Kernelization and Sparseness: the case of Dominating Set

DOI10.4230/LIPICS.STACS.2016.31zbMATH Open1388.68110arXiv1411.4575OpenAlexW2963587624MaRDI QIDQ4601883

Author name not available (Why is that?)

Publication date: 24 January 2018

Abstract: We prove that for every positive integer $r$ and for every graph class $mathcalG$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from $mathcalG$. Moreover, when $mathcalG$ is only assumed to be nowhere dense, then we give an almost linear kernel on $mathcalG$ for the classic Dominating Set problem, i.e., for the case $r=1$. These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$-Dominating Set. However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related Connected Dominating Set problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on $H$-topological-minor-free graphs. Also, we prove that for any somewhere dense class $mathcalG$, there is some $r$ for which $r$-Dominating Set is W[$2$]-hard on $mathcalG$. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of $r$-Dominating Set on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.

Full work available at URL: https://arxiv.org/abs/1411.4575

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Kernelization and Sparseness: the case of Dominating Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601883)