Document Open Access Logo

Detecting Cliques in CONGEST Networks

Authors Artur Czumaj, Christian Konrad

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.16.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Artur Czumaj
  • Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, UK
Christian Konrad
  • Department of Computer Science, University of Bristol, UK

Funding

  • Czumaj, Artur: Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC award EP/D063191/1, by EPSRC award EP/N011163/1, and by an IBM Faculty Award.
  • Konrad, Christian: Most of work on this paper has been carried out while the author was at the University of Warwick, where he was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by EPSRC award EP/N011163/1.

Cite AsGet BibTex

Artur Czumaj and Christian Konrad. Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.16

Abstract

The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H, the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique K_l in the classical distributed CONGEST model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. Our first and main result is a lower bound, showing that detecting K_l requires Omega(sqrt{n} / b) communication rounds, for every 4 <=l <=sqrt{n}, and Omega(n / (l b)) rounds for every l >= sqrt{n}, where b is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for K_4 detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Networks → Network algorithms
Keywords
  • Lower bounds
  • CONGEST
  • subgraph detection
  • two-party communication

Metrics

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

References

  1. Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Computing, 24(2):79-89, 2011. Google Scholar
  2. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 43-56, 2016. Google Scholar
  3. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proceedings of the 35th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 143-152, 2015. Google Scholar
  4. 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), pages 10:1-10:16, 2017. Google Scholar
  5. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. CoRR, abs/1807.06624, 2018. URL: http://arxiv.org/abs/1807.06624.
  6. 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), pages 195-209, 2012. Google Scholar
  7. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. Google Scholar
  8. 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. Google Scholar
  9. 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), pages 153-162, New York, NY, USA, 2018. ACM. Google Scholar
  10. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. In Proceedings of the 29th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 153-162, 2017. Google Scholar
  11. 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. Google Scholar
  12. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the 37th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 381-389, 2017. Google Scholar
  13. Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. John Wiley &Sons, 2011. Google Scholar
  14. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992. Google Scholar
  15. 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), pages 4:1-4:16, 2017. Google Scholar
  16. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  17. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. Tight bounds for distributed graph computations. CoRR, abs/1602.08481, 2016. Google Scholar
  18. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 2000. 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