Document Open Access Logo

Distributed Subgraph Finding: Progress and Challenges (Invited Talk)

Author Keren Censor-Hillel

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.3.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement no. 755839.

Acknowledgements

The author thanks Francois Le Gall for clarifications and Dean Leitersdorf for useful feedback on a preliminary version of this survey.

Cite As Get BibTex

Keren Censor-Hillel. Distributed Subgraph Finding: Progress and Challenges (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.3

Abstract

This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted variants of subgraph finding problems in various models of distributed computing, and states intriguing open questions.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • distributed algorithms
  • subgraph finding
  • limited bandwidth

Metrics

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

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen. Fooling views: a new lower bound technique for distributed computations under congestion. Distributed Computing, 33:545-–559, 2020. URL: https://doi.org/10.1007/s00446-020-00373-4.
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), 2021. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. URL: https://doi.org/10.1016/j.jcss.2003.11.006.
  5. Matthias Bonne and Keren Censor-Hillel. Distributed detection of cliques in dynamic networks. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 132:1-132:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.132.
  6. Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Comput., 24(2):79-89, 2011. URL: https://doi.org/10.1007/s00446-011-0132-x.
  7. Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. Google Scholar
  8. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. Distributed Computing, 2020. URL: https://doi.org/10.1007/s00446-020-00380-5.
  9. 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: https://doi.org/10.1007/s00446-018-0324-8.
  10. Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast distributed algorithms for girth, cycles and small subgraphs. In Proceedings of the 34th International Symposium on Distributed Computing (DISC), pages 33:1-33:17, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.33.
  11. Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf. On distributed listing of cliques. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 474-482, 2020. URL: https://doi.org/10.1145/3382734.3405742.
  12. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. Distributed Computing, 32(6):461-478, 2019. URL: https://doi.org/10.1007/s00446-016-0270-2.
  13. Keren Censor-Hillel, Victor I. Kolobov, and Gregory Schwartzman. Finding subgraphs in highly dynamic networks. CoRR, abs/2009.08208, 2020, To appear in SPAA. URL: http://arxiv.org/abs/2009.08208.
  14. Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. Sparse matrix multiplication and triangle listing in the congested clique model. Theor. Comput. Sci., 809:45-60, 2020. URL: https://doi.org/10.1016/j.tcs.2019.11.006.
  15. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 821-840, 2019. URL: https://doi.org/10.5555/3310435.3310486.
  16. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 66-73, 2019. URL: https://doi.org/10.1145/3293611.3331618.
  17. Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 377-388, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00043.
  18. Artur Czumaj and Christian Konrad. Detecting cliques in CONGEST networks. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 16:1-16:15, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.16.
  19. Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting - (extended abstract). In Proceedings of the 26th International Symposium on Distributed Computing (DISC), pages 195-209, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_14.
  20. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  21. Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-time distributed algorithms for detecting small cliques and even cycles. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), pages 15:1-15:16, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.15.
  22. Paul Erdös. On sequences of integers no one of which divides the product of two others and on some related problems. Inst. Math. Mech. Univ. Tomsk, 2:74-82, 1938. Google Scholar
  23. 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 Proceedings of the 31st International Symposium on Distributed Computing (DISC), pages 15:1-15:30, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.15.
  24. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 153-162, 2018. URL: https://doi.org/10.1145/3210377.3210401.
  25. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. In Christian Scheideler and Mohammad Taghi Hajiaghayi, editors, Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24-26, 2017, pages 153-162. ACM, 2017. URL: https://doi.org/10.1145/3087556.3087571.
  26. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 342-356. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_25.
  27. François Le Gall. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 57-70, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_5.
  28. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 131-140, 2017. URL: https://doi.org/10.1145/3087801.3087827.
  29. Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 31:1-31:16, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.31.
  30. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  31. Tzlil Gonen and Rotem Oshman. Lower bounds for subgraph detection in the CONGEST model. In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS), pages 6:1-6:16, 2017. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.6.
  32. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pages 212-219, 1996. URL: https://doi.org/10.1145/237814.237866.
  33. Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large cuts with local algorithms on triangle-free graphs. Electron. J. Comb., 24(4):P4.21, 2017. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p21.
  34. Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang. The communication complexity of set intersection and multiple equality testing. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1715-1732, 2020. URL: https://doi.org/10.1137/1.9781611975994.105.
  35. Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 84-93, 2019. URL: https://doi.org/10.1145/3293611.3331628.
  36. 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), pages 381-389, 2017. URL: https://doi.org/10.1145/3087801.3087811.
  37. Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 23:1-23:13, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.49.
  38. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discret. Math., 5(4):545-557, 1992. URL: https://doi.org/10.1137/0405044.
  39. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed computation of large-scale graph problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391-410, 2015. URL: https://doi.org/10.1137/1.9781611973730.28.
  40. Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST. In James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão, editors, 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, volume 95 of LIPIcs, pages 4:1-4:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.4.
  41. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 42-50, 2013. URL: https://doi.org/10.1145/2484239.2501983.
  42. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  43. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput., 35(1):120-131, 2005. URL: https://doi.org/10.1137/S0097539704441848.
  44. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 405-414, 2018. Google Scholar
  45. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. Google Scholar
  46. Seth Pettie and Hsin-Hao Su. Fast distributed coloring algorithms for triangle-free graphs. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 of Lecture Notes in Computer Science, pages 681-693. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39212-2_59.
  47. Alexander A. Razborov. On the distributional complexity of disjontness. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 249-253. Springer, 1990. URL: https://doi.org/10.1007/BFb0032036.
  48. Paul Turán. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48:436-452, 1941. 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