Document Open Access Logo

A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs

Authors Marthe Bonamy , Linda Cook, Carla Groenland , Alexandra Wesolek

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.13.pdf
  • Filesize: 0.79 MB
  • 18 pages

Document Identifiers

Author Details

Marthe Bonamy
  • CNRS, LaBRI, Université de Bordeaux, France
Linda Cook
  • Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, Republic of Korea
Carla Groenland
  • Utrecht University, The Netherlands
Alexandra Wesolek
  • Department of Mathematics, Simon Fraser University, Burnaby, Canada

Funding

  • Bonamy, Marthe: Supported by the ANR project GrR (ANR-18-CE40-0032).
  • Cook, Linda: This work was supported by AFOSR grant A9550-19-1-0187, NSF grant DMS-1800053 and the Institute for Basic Science (IBS-R029-C1).
  • Groenland, Carla: Supported by the European Research Council Horizon 2020 project CRACKNP (grant agreement no. 853234).
  • Wesolek, Alexandra: Supported by the Vanier Canada Graduate Scholarships program.

Acknowledgements

We thank the referees for helpful comments which improved the presentation of the paper.

Cite As Get BibTex

Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.13

Abstract

We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a (5-ε)-approximation, for any ε > 0. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • Outerplanar graphs
  • dominating set
  • LOCAL model
  • constant-factor approximation algorithm

Metrics

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

Related Versions

References

  1. Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. Distributed domination on graph classes of bounded expansion. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA quotesingle18, pages 143-151, 2018. Google Scholar
  2. Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. A local constant factor mds approximation for bounded genus graphs. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC quotesingle16, page 227–233, 2016. Google Scholar
  3. Sharareh Alipour, Ehsan Futuhi, and Shayan Karimi. On distributed algorithms for minimum dominating set problem, from theory to application, 2021. URL: http://arxiv.org/abs/2012.04883.
  4. Sharareh Alipour and Amir Jafari. A local constant approximation factor algorithm for minimum dominating set of certain planar graphs. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA quotesingle20, pages 501-502, 2020. Google Scholar
  5. Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. Distributed dominating set approximations beyond planar graphs. ACM Transactions on Algorithms (TALG), 15(3):1-18, 2019. Google Scholar
  6. Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A tight local algorithm for the minimum dominating set problem in outerplanar graphs, 2021. URL: http://arxiv.org/abs/2108.02697.
  7. Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In International Symposium on Distributed Computing, DISC quotesingle08, pages 78-92. Springer, 2008. Google Scholar
  8. Laurent Feuilloley. Bibliography of distributed approximation beyond bounded degree, 2020. URL: http://arxiv.org/abs/2001.08510.
  9. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., San Francisco, 1979. Google Scholar
  10. Daniel Gonçalves. Edge partition of planar graphs into two outerplanar graphs. In Proceedings of the thirty-seventh annual ACM Symposium on Theory of Computing, STOC quotesingle05, pages 504-512, 2005. Google Scholar
  11. Miikka Hilke, Christoph Lenzen, and Jukka Suomela. Brief announcement: local approximability of minimum dominating set on planar graphs. In Proceedings of the 2014 ACM symposium on Principles of Distributed Computing, PODC quotesingle14, pages 344-346, 2014. Google Scholar
  12. Simeon Kublenz, Sebastian Siebertz, and Alexandre Vigny. Constant round distributed domination on graph classes with bounded expansion, 2021. URL: http://arxiv.org/abs/2012.02701.
  13. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM (JACM), 63(2):1-44, 2016. Google Scholar
  14. Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer. What can be approximated locally? case study: Dominating sets in planar graphs. In Proceedings of the twentieth annual Symposium on Parallelism in Algorithms and Architectures, SPAA quotesingle08, pages 46-54, 2008. Google Scholar
  15. Crispin St. John Alvah. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society (JLMS), s1-39(1):12-12, 1964. Google Scholar
  16. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC quotesingle97, page 475–484, 1997. Google Scholar
  17. Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):1-40, 2013. Google Scholar
  18. Wojciech Wawrzyniak. Brief announcement: a local approximation algorithm for mds problem in anonymous planar networks. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC quotesingle13, pages 406-408, 2013. Google Scholar
  19. Wojciech Wawrzyniak. A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Information Processing Letters (IPL), 114(3):94-98, 2014. Google Scholar
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 About DROPS Imprint Privacy Contact