Document Open Access Logo

Dominating Sets and Connected Dominating Sets in Dynamic Graphs

Authors Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis, David Saulpic

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.35.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Niklas Hjuler
  • University of Copenhagen, Denmark
Giuseppe F. Italiano
  • LUISS University, Rome, Italy
Nikos Parotsidis
  • University of Rome Tor Vergata, Italy
David Saulpic
  • ENS Paris, France

Funding

This work was done while Niklas Hjuler and David Saulpic were visiting University of Rome Tor Vergata.

Cite As Get BibTex

Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis, and David Saulpic. Dominating Sets and Connected Dominating Sets in Dynamic Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.35

Abstract

In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present algorithms that maintain a solution under edge insertions and edge deletions in time O(Delta * polylog n) per update, where Delta is the maximum vertex degree in the graph. In both cases, we achieve an approximation ratio of O(log n), which is optimal up to a constant factor (under the assumption that P != NP). Although those two problems have been widely studied in the static and in the distributed settings, to the best of our knowledge we are the first to present efficient algorithms in the dynamic setting.
As a further application of our approach, we also present an algorithm that maintains a Minimal Dominating Set in O(min(Delta, sqrt{m})) per update.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dominating Set
  • Connected Dominating Set
  • Dynamic Graph Algorithms

Metrics

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

References

  1. Raghavendra Addanki and Barna Saha. Fully Dynamic Set Cover-Improved and Simple. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.03197.
  2. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, 2018. Google Scholar
  3. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully Dynamic Maximal Independent Set with Sublinear in n Update Time, pages 1919-1936. SIAM, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.116.
  4. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1899-1918. SIAM, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.115.
  5. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 692-711. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  6. Sivakumar R Bevan Das and V Bharghavan. Routing in ad-hoc networks using a virtual backbone. In Proceedings of the 6th International Conference on Computer Communications and Networks (IC3N'97), pages 1-20, 1997. Google Scholar
  7. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-20. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  8. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing, 47(3):859-887, 2018. Google Scholar
  9. Sergiy Butenko, Xiuzhen Cheng, Carlos A Oliveira, and Panos M Pardalos. A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks. In Recent developments in cooperative control and optimization, pages 61-73. Springer, 2004. Google Scholar
  10. Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, and Ding-Zhu Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks: An International Journal, 42(4):202-208, 2003. Google Scholar
  11. V. Chvatal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4(3):233-235, 1979. URL: http://www.jstor.org/stable/3689577.
  12. Camil Demetrescu and Giuseppe F. Italiano. A New Approach to Dynamic All Pairs Shortest Paths. J. ACM, 51(6):968-992, 2004. Google Scholar
  13. Ding-Zhu Du and Peng-Jun Wan. Connected dominating set: theory and applications, volume 77. Springer Science &Business Media, 2012. Google Scholar
  14. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. Sudipto Guha and Samir Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374-387, 1998. Google Scholar
  17. Leonidas Guibas, Nikola Milosavljević, and Arik Motskin. Connected dominating sets on dynamic geometric graphs. Computational Geometry, 46(2):160-172, 2013. Google Scholar
  18. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 537-550. ACM, 2017. Google Scholar
  19. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for Maximal Independent Set and other problems. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.01823.
  20. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 548-557. IEEE, 2013. Google Scholar
  21. Johan Håstad. Clique is hard to approximate withinn 1- ε. Acta Mathematica, 182(1):105-142, 1999. Google Scholar
  22. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic Deterministic Fully-dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-edge, and Biconnectivity. J. ACM, 48(4):723-760, 2001. Google Scholar
  23. Lujun Jia, Rajmohan Rajaraman, and Torsten Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193-205, 2002. Google Scholar
  24. Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm, 1992. Google Scholar
  25. Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. Distributed Computing, 17(4):303-310, 2005. Google Scholar
  26. D. Nanongkai, T. Saranurak, and C. Wulff-Nilsen. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 950-961, October 2017. Google Scholar
  27. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):7, 2016. Google Scholar
  28. E Sampathkumar and HB Walikar. The connected domination number of a graph. J. Math. Phys, 1979. Google Scholar
  29. Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of computer and system sciences, 26(3):362-391, 1983. Google Scholar
  30. S. Solomon. Fully Dynamic Maximal Matching in Constant Update Time. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 325-334, October 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.43.
  31. Jie Wu and Hailan Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pages 7-14. ACM, 1999. 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