Document Open Access Logo

Lower Bounds for Induced Cycle Detection in Distributed Computing

Authors François Le Gall, Masayuki Miyamoto

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.58.pdf
  • Filesize: 0.89 MB
  • 19 pages

Document Identifiers

Author Details

François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan
Masayuki Miyamoto
  • Graduate School of Mathematics, Nagoya University, Japan

Funding

This work was partially supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP20H00579, JP20H04139, JP21H04879 and by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grants No. JPMXS0118067394 and JPMXS0120319794.

Acknowledgements

The authors are grateful to Keren Censor-Hillel, Orr Fischer, Pierre Fraigniaud, Dean Leitersdorf and Rotem Oshman for helpful discussions and comments, and Shin-ichi Minato for his support.

Cite AsGet BibTex

François Le Gall and Masayuki Miyamoto. Lower Bounds for Induced Cycle Detection in Distributed Computing. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.58

Abstract

The distributed subgraph detection asks, for a fixed graph H, whether the n-node input graph contains H as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a lot of attention recently. In this paper we consider the induced variant of subgraph detection, where the goal is to decide whether the n-node input graph contains H as an induced subgraph or not. We first show a Ω̃(n) lower bound for detecting the existence of an induced k-cycle for any k ≥ 4 in the CONGEST model. This lower bound is tight for k = 4, and shows that the induced variant of k-cycle detection is much harder than the non-induced version. This lower bound is proved via a reduction from two-party communication complexity. We complement this result by showing that for 5 ≤ k ≤ 7, this Ω̃(n) lower bound cannot be improved via the two-party communication framework. We then show how to prove stronger lower bounds for larger values of k. More precisely, we show that detecting an induced k-cycle for any k ≥ 8 requires Ω̃(n^{2-Θ{(1/k)}}) rounds in the CONGEST model, nearly matching the known upper bound Õ(n^{2-Θ{(1/k)}}) of the general k-node subgraph detection (which also applies to the induced version) by Eden, Fiat, Fischer, Kuhn, and Oshman [DISC 2019]. Finally, we investigate the case where H is the diamond (the diamond is obtained by adding an edge to a 4-cycle, or equivalently removing an edge from a 4-clique), and show non-trivial upper and lower bounds on the complexity of the induced version of diamond detecting and listing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Lower bounds and information complexity
Keywords
  • Distributed computing
  • Lower bounds
  • Subgraph detection

Metrics

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

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016), pages 29-42, 2016. Google Scholar
  2. Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 2878-2891, 2021. Google Scholar
  3. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. Distributed Computing, 32(6):41-57, 2019. Google Scholar
  4. 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 2020), pages 33:1-33:17, 2020. Google Scholar
  5. Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf. On distributed listing of cliques. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 474-482, 2020. Google Scholar
  6. 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. Google Scholar
  7. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017), pages 10:1-10:16, 2017. Google Scholar
  8. 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 2019), pages 821-840, 2019. Google Scholar
  9. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 66-73, 2019. Google Scholar
  10. Derek G. Corneil, Yehoshua Perl, and Lorna K Stewart. A linear recognition algorithm for cographs. SIAM Journal on Computing, 14(4):926-934, 1985. Google Scholar
  11. Artur Czumaj and Christian Konrad. Detecting cliques in CONGEST networks. Distributed Computing, 33(6):533-543, 2020. Google Scholar
  12. 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
  13. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 367-376, 2014. Google Scholar
  14. 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), pages 15:1-15:16, 2019. Google Scholar
  15. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1-3):57-67, 2004. Google Scholar
  16. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 153-162, 2018. Google Scholar
  17. Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, and Ioan Todinca. Distributed subgraph detection. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.03996.
  18. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. ACM Transactions on Parallel Computing (TOPC), 6(3):1-20, 2019. Google Scholar
  19. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016), 2016. Google Scholar
  20. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413-423, 1978. Google Scholar
  21. 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 2020), pages 23:1-23:13, 2020. Google Scholar
  22. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 381-389, 2017. Google Scholar
  23. Janne H. Korhonen and Amir Nikabadi. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters, 2021. URL: http://arxiv.org/abs/2109.06561.
  24. Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST. In Proceedings of the 21th International Conference on Principles of Distributed Systems (OPODIS 2017), pages 4:1-4:16, 2017. Google Scholar
  25. Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and detecting small subgraphs via equations. SIAM Journal on Discrete Mathematics, 27(2):892-909, 2013. Google Scholar
  26. François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 337-346, 2018. Google Scholar
  27. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  28. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 405-414, 2018. Google Scholar
  29. Alexander A Razborov. On the distributional complexity of disjointness. In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP 1990), pages 249-253, 1990. Google Scholar
  30. Virginia Vassilevska Williams, Joshua R Wang, Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Proceedings of the 24th annual ACM-SIAM symposium on Discrete algorithms (SODA 2014), pages 1671-1680, 2014. 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 Imprint Privacy Contact