Document Open Access Logo

Distributed Detection of Cliques in Dynamic Networks

Authors Matthias Bonne, Keren Censor-Hillel

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.132.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Matthias Bonne
  • Department of Computer Science, Technion, Haifa, Israel
Keren Censor-Hillel
  • Department of Computer Science, Technion, Haifa, Israel

Acknowledgements

This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under grant agreement no. 755839.

Cite AsGet BibTex

Matthias Bonne and Keren Censor-Hillel. Distributed Detection of Cliques in Dynamic Networks. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 132:1-132:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.132

Abstract

This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: - The bandwidth complexity of 1-round dynamic triangle detection or listing is Theta(1). - The bandwidth complexity of 1-round dynamic triangle membership listing is Theta(1) for node/edge deletions, Theta(n^{1/2}) for edge insertions, and Theta(n) for node insertions. - The bandwidth complexity of 1-round dynamic triangle membership detection is Theta(1) for node/edge deletions, O(log n) for edge insertions, and Theta(n) for node insertions. Most of our upper and lower bounds are tight. Additionally, we provide almost always tight upper and lower bounds for larger cliques.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Distributed algorithms
Keywords
  • distributed computing
  • subgraph detection
  • dynamic graphs

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen. Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion. CoRR, abs/1711.01623, 2017. URL: http://arxiv.org/abs/1711.01623.
  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), pages 815-826, 2018. URL: http://dx.doi.org/10.1145/3188745.3188922.
  3. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1919-1936, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.116.
  4. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Local Distributed Algorithms in Highly Dynamic Networks. CoRR, abs/1802.10199, 2018. URL: http://arxiv.org/abs/1802.10199.
  5. Matthias Bonne and Keren Censor-Hillel. Distributed Detection of Cliques in Dynamic Networks. CoRR, abs/1904.11440, 2019. URL: http://arxiv.org/abs/1904.11440.
  6. Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Computing, 24(2):79-89, 2011. URL: http://dx.doi.org/10.1007/s00446-011-0132-x.
  7. Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks. CoRR, abs/1901.04008, 2019. Google Scholar
  8. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. Distributed Computing, 32(1):41-57, 2019. URL: http://dx.doi.org/10.1007/s00446-018-0324-8.
  9. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal Dynamic Distributed MIS. In Proceedings of the 2016 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.
  10. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed Triangle Detection via Expander Decomposition. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 821-840, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.51.
  11. Artur Czumaj and Christian Konrad. Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 16:1-16:15, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2018.16.
  12. Shlomi Dolev. Self-Stabilization. MIT Press, 2000. Google Scholar
  13. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 367-376, 2014. URL: http://dx.doi.org/10.1145/2611462.2611493.
  14. Yuhao Du and Hengjie Zhang. Improved Algorithms for Fully Dynamic Maximal Independent Set. CoRR, abs/1804.08908, 2018. URL: http://arxiv.org/abs/1804.08908.
  15. P. Erdös. On extremal problems of graphs and generalized graphs. Israel Journal of Mathematics, 2(3):183-190, September 1964. URL: http://dx.doi.org/10.1007/BF02759942.
  16. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 15:1-15:30, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.15.
  17. Guy Even, Reut Levi, and Moti Medina. Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model. CoRR, abs/1705.04898, 2017. URL: http://arxiv.org/abs/1705.04898.
  18. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and Impossibilities for Distributed Subgraph Detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pages 153-162, 2018. URL: http://dx.doi.org/10.1145/3210377.3210401.
  19. Orr Fischer, Tzlil Gonen, and Rotem Oshman. Distributed Property Testing for Subgraph-Freeness Revisited. CoRR, abs/1705.04033, 2017. URL: http://arxiv.org/abs/1705.04033.
  20. Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, and Ioan Todinca. Distributed Subgraph Detection. CoRR, abs/1706.03996, 2017. URL: http://arxiv.org/abs/1706.03996.
  21. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed Testing of Excluded Subgraphs. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, pages 342-356, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_25.
  22. Tzlil Gonen and Rotem Oshman. Lower Bounds for Subgraph Detection in the CONGEST Model. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, pages 6:1-6:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2017.6.
  23. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for Maximal Independent Set and other problems. CoRR, abs/1804.01823, 2018. URL: http://arxiv.org/abs/1804.01823.
  24. Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large Cuts with Local Algorithms on Triangle-Free Graphs. Electr. J. Comb., 24(4):P4.21, 2017. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p21.
  25. Taisuke Izumi and François Le Gall. Triangle Finding and Listing in CONGEST Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 381-389, 2017. URL: http://dx.doi.org/10.1145/3087801.3087811.
  26. Michael König and Roger Wattenhofer. On Local Fixing. In OPODIS, volume 8304 of Lecture Notes in Computer Science, pages 191-205. Springer, 2013. Google Scholar
  27. Janne H. Korhonen and Joel Rybicki. Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, pages 4:1-4:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2017.4.
  28. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations. In SPAA, pages 405-414. ACM, 2018. Google Scholar
  29. Merav Parter, David Peleg, and Shay Solomon. Local-on-Average Distributed Tasks. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 220-239, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch17.
  30. Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Inf. Comput., 243:263-280, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.018.
  31. Shay Solomon. Fully Dynamic Maximal Matching in Constant Update Time. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 325-334, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.43.
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