×

Kernelization and sparseness: the case of dominating set. (English) Zbl 1388.68110

Ollinger, Nicolas (ed.) et al., 33rd symposium on theoretical aspects of computer science, STACS 2016, Orléans, France, February 17–20, 2016. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-001-9). LIPIcs – Leibniz International Proceedings in Informatics 47, Article 31, 14 p. (2016).
Summary: We prove that for every positive integer \(r\) and for every graph class \({\mathcal G}\) of bounded expansion, the \(r\)-Dominating Set problem admits a linear kernel on graphs from \({\mathcal G}\). Moreover, in the more general case when \({\mathcal G}\) is only assumed to be nowhere dense, we give an almost linear kernel on \({\mathcal G}\) 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 [J. Alber et al., J. ACM 51, No. 3, 363–384 (2004; Zbl 1192.68337); H. L. Bodlaender et al., in: Proceedings of the 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Los Alamitos, CA: IEEE Computer Society. 629–638 (2009; Zbl 1292.68089); F. V. Fomin et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 503–510 (2010; Zbl 1288.68116); “Linear kernels for (connected) dominating set on \(H\)-minor-free graphs”, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 82–93 (2012); LIPICS – Leibniz Int. Proc. Inform. 20, 92–103 (2013; Zbl 1354.68120)]. 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 [Zbl 1354.68120]. Also, we prove that for any somewhere dense class \({\mathcal G}\), there is some \(r\) for which \(r\)-Dominating Set is W[2]-hard on \({\mathcal G}\). 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.
For the entire collection see [Zbl 1338.68009].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv