Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

Authors Keren Censor-Hillel , Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman



PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.33.pdf
  • Filesize: 1.2 MB
  • 17 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Technion - Israel Institute of Technology, Haifa, Israel
Orr Fischer
  • Tel-Aviv University, Israel
Tzlil Gonen
  • Tel-Aviv University, Israel
François Le Gall
  • Nagoya University, Japan
Dean Leitersdorf
  • Technion - Israel Institute of Technology, Haifa, Israel
Rotem Oshman
  • Tel-Aviv University, Israel

Cite AsGet BibTex

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 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.33

Abstract

In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • cycles
  • girth
  • Congested Clique
  • CONGEST

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  3. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 74-83, 2019. Google Scholar
  4. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. Distributed Comput., 32(6):461-478, 2019. URL: https://doi.org/10.1007/s00446-016-0270-2.
  5. 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.
  6. 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), pages 821-840, 2019. Google Scholar
  7. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 66-73, 2019. Google Scholar
  8. Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting. In Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012), pages 195-209, 2012. Google Scholar
  9. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 367-376, 2014. Google Scholar
  10. 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 2019), volume 146 of LIPIcs, pages 15:1-15:16, 2019. Google Scholar
  11. Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. A note on the hardness of proving distributed lower bounds for triangle-freeness. https://www.cs.tau.ac.il/~roshman/papers/EFFKO19_triangle_note.pdf, 2020.
  12. 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), pages 153-162, 2018. URL: https://doi.org/10.1145/3210377.3210401.
  13. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1150-1162, 2012. Google Scholar
  14. Zoltán Füredi and Miklós Simonovits. The History of Degenerate (Bipartite) Extremal Graph Problems, pages 169-264. Springer Berlin Heidelberg, 2013. Google Scholar
  15. 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.
  16. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC 2012), pages 355-364, 2012. Google Scholar
  17. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978. URL: https://doi.org/10.1137/0207033.
  18. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 381-389, 2017. Google Scholar
  19. Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST. In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS 2017), pages 4:1-4:16, 2017. Google Scholar
  20. 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 2016), pages 57-70, 2016. Google Scholar
  21. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC 2013), pages 42-50, 2013. Google Scholar
  22. Andrzej Lingas and Eva-Marta Lundell. Efficient approximation algorithms for shortest cycles in undirected graphs. Inf. Process. Lett., 109(10):493-498, 2009. Google Scholar
  23. 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 2018), pages 405-414, 2018. Google Scholar
  24. David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), pages 660-672, 2012. Google Scholar
  25. Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation, 243:263-280, 2015. Google Scholar
  26. Liam Roditty and Roei Tov. Approximating the girth. ACM Trans. Algorithms, 9(2):15:1-15:13, 2013. Google Scholar
  27. Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pages 180-189, 2011. Google Scholar
  28. Liam Roditty and Virginia Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 833-845, 2012. 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