Document Open Access Logo

Fully Dynamic MIS in Uniformly Sparse Graphs

Authors Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.92.pdf
  • Filesize: 436 kB
  • 14 pages

Document Identifiers

Author Details

Krzysztof Onak
  • IBM Research, TJ Watson Research Center, Yorktown Heights, New York, USA
Baruch Schieber
  • IBM Research, TJ Watson Research Center, Yorktown Heights, New York, USA
Shay Solomon
  • IBM Research, TJ Watson Research Center, Yorktown Heights, New York, USA
Nicole Wein
  • Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

Funding

  • Solomon, Shay: Supported by the IBM Herman Goldstine Postdoctoral Fellowship.
  • Wein, Nicole: Supported by an NSF Graduate Fellowship.

Cite AsGet BibTex

Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully Dynamic MIS in Uniformly Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 92:1-92:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.92

Abstract

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity alpha, the amortized update time of our algorithm is O(alpha^2 * log^2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of "real world" graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m^{3/8 - epsilon}, for any constant epsilon > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m^{1/2}.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Dynamic graph algorithms
Keywords
  • dynamic graph algorithms
  • independent set
  • sparse graphs
  • graph arboricity

Metrics

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

Related Versions

  • A full version of the paper is available at [Onak et al., 2018].

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90019-2.
  2. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2018. Google Scholar
  3. Edvin Berglin and Gerth Stølting Brodal. A simple greedy algorithm for dynamic graph orientation. In Proc. 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, pages 12:1-12:12, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.12.
  4. Guy E. Blelloch, Jeremy T. Fineman, and Julian Shun. Greedy sequential maximal independent set and matching are parallel on average. In Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2012, Pittsburgh, PA, USA, June 25-27, 2012, pages 308-317, 2012. URL: http://dx.doi.org/10.1145/2312005.2312058.
  5. Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In Proc. 6th International Workshop on Algorithms and Data Structures WADS, pages 342-351. Springer-Verlag, 1999. Google Scholar
  6. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proc. ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217-226, 2016. URL: http://dx.doi.org/10.1145/2933057.2933083.
  7. Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport. Leader election in shared spectrum radio networks. In Proc. ACM Symposium on Principles of Distributed Computing, PODC 2012, Funchal, Madeira, Portugal, July 16-18, 2012, pages 215-224, 2012. URL: http://dx.doi.org/10.1145/2332432.2332470.
  8. Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy MIS. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2152-2160, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.140.
  9. Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In Proc. Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG, pages 159-167, 2006. URL: http://dx.doi.org/10.1007/11917496_15.
  10. Meng He, Ganggui Tang, and Norbert Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In Proc. Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, pages 128-140, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_11.
  11. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: http://dx.doi.org/10.1137/0202019.
  12. Tomasz Jurdzinski and Dariusz R. Kowalski. Distributed backbone structure for algorithms in the SINR model of wireless networks. In Proc. Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012, pages 106-120, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33651-5_8.
  13. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Proc. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Part II, pages 532-543, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_45.
  14. Lukasz Kowalik. Adjacency queries in dynamic sparse graphs. Inf. Process. Lett., 102(5):191-195, 2007. URL: http://dx.doi.org/10.1016/j.ipl.2006.12.006.
  15. Lukasz Kowalik and Maciej Kurowski. Short path queries in planar graphs in constant time. In Proc. 35th Annual ACM Symposium on Theory of Computing, STOC, pages 143-148, 2003. Google Scholar
  16. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Initializing newly deployed ad hoc and sensor networks. In Proc. 10th Annual International Conference on Mobile Computing and Networking, MOBICOM 2004, Philadelphia, PA, USA, September 26 - October 1, 2004, pages 260-274, 2004. URL: http://dx.doi.org/10.1145/1023720.1023746.
  17. Nathan Linial. Distributive graph algorithms-global solutions from local data. In Proc. 28th Annual Symposium on Foundations of Computer Science, FOCS 1987, Los Angeles, California, USA, 27-29 October 1987, pages 331-335, 1987. URL: http://dx.doi.org/10.1109/SFCS.1987.20.
  18. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036-1053, 1986. URL: http://dx.doi.org/10.1137/0215074.
  19. Crispin St.J. Nash-Williams. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 36(1):445-–450, 1961. Google Scholar
  20. Crispin St.J. Nash-Williams. Decomposition of finite graphs into forests. J. London Math. Soc., 39(1):12, 1964. Google Scholar
  21. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proc. Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, June 1-4, 2013, pages 745-754, 2013. URL: http://dx.doi.org/10.1145/2488608.2488703.
  22. Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 327-336, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.81.
  23. Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs. arXiv CoRR, 2018. Google Scholar
  24. William T. Tutte. On the problem of decomposing a graph into n connected factors. J. London Math. Soc., 36(1):221-230, 1961. Google Scholar
  25. Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, and Francis C. M. Lau. Distributed (Δ+1)-coloring in the physical model. Theor. Comput. Sci., 553:37-56, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.05.016.
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