Document Open Access Logo

A General Kernelization Technique for Domination and Independence Problems in Sparse Classes

Authors Carl Einarson, Felix Reidl

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.11.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Carl Einarson
  • Royal Holloway, University of London, UK
Felix Reidl
  • Birkbeck, University of London, UK

Cite AsGet BibTex

Carl Einarson and Felix Reidl. A General Kernelization Technique for Domination and Independence Problems in Sparse Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.11

Abstract

We unify and extend previous kernelization techniques in sparse classes [Jochen Alber et al., 2004; Pilipczuk and Siebertz, 2018] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r,c)-Dominating Set, (r,c)-Scattered Set, Total r-Domination, r-Roman Domination, and a problem we call (r,[λ,μ])-Domination (implying a bikernel for r-Perfect Code). At the cost of slightly changing the output graph class our bikernels can be turned into kernels. We also demonstrate how these constructions can be combined to create "multikernels", meaning graphs that represent kernels for multiple problems at once.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Dominating Set
  • Independence
  • Kernelization
  • Bounded Expansion

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. URL: https://doi.org/10.1145/990308.990309.
  2. Noga Alon and Shai Gutner. Kernels for the dominating set problem on graphs with an excluded minor. Electron. Colloquium Comput. Complex., 15(066), 2008. URL: http://eccc.hpi-web.de/eccc-reports/2008/TR08-066/index.html.
  3. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, 2016. URL: https://doi.org/10.1145/2973749.
  4. Mustapha Chellali, Odile Favaron, Adriana Hansberg, and Lutz Volkmann. k-domination and k-independence in graphs: A survey. Graphs Comb., 28(1):1-55, 2012. URL: https://doi.org/10.1007/s00373-011-1040-3.
  5. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  6. Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and sparseness: the case of dominating set. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, volume 47 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.31.
  7. Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb., 34(5):833-840, 2013. URL: https://doi.org/10.1016/j.ejc.2012.12.004.
  8. Zdeněk Dvořák. On distance-dominating and-independent sets in sparse graphs. Journal of Graph Theory, 91(2):162-173, 2019. URL: https://doi.org/10.1002/jgt.22426.
  9. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 503-510. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.43.
  10. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 82-93. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.7.
  11. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms, 14(1):6:1-6:31, 2018. URL: https://doi.org/10.1145/3155298.
  12. Shai Gutner. Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor. In Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 246-257. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_20.
  13. Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The generalised colouring numbers on classes of bounded expansion. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, volume 58 of LIPIcs, pages 85:1-85:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.85.
  14. Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Polynomial kernels and wideness properties of nowhere dense graph classes. ACM Trans. Algorithms, 15(2):24:1-24:19, 2019. URL: https://doi.org/10.1145/3274652.
  15. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion i. decompositions. Eur. J. Comb., 29(3):760-776, 2008. URL: https://doi.org/10.1016/j.ejc.2006.07.013.
  16. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  17. Michał Pilipczuk and Sebastian Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.05675.
  18. Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos S. Stavropoulos. Characterising bounded expansion by neighbourhood complexity. Eur. J. Comb., 75:152-168, 2019. URL: https://doi.org/10.1016/j.ejc.2018.08.001.
  19. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discret. Math., 309(18):5562-5568, 2009. URL: https://doi.org/10.1016/j.disc.2008.03.024.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact