Document Open Access Logo

Deterministic Subgraph Detection in Broadcast CONGEST

Authors Janne H. Korhonen, Joel Rybicki

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.4.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Janne H. Korhonen
Joel Rybicki

Cite As Get BibTex

Janne H. Korhonen and Joel Rybicki. Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.4

Abstract

We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation:
- For any constant k, detecting k-paths and trees on k nodes can be done in O(1) rounds.
- For any constant k, detecting k-cycles and pseudotrees on k nodes can be done in O(n)
rounds.
- On d-degenerate graphs, cliques and 4-cycles can be enumerated in O(d + log n) rounds, and
5-cycles in O(d2 + log n) rounds.
In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for d-degenerate graphs can be improved to O(d/logn) and O(d2/logn), respect- ively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.

Subject Classification

Keywords
  • distributed computing
  • subgraph detection
  • CONGEST model
  • lower bounds

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. URL: http://dx.doi.org/10.1007/s00446-009-0088-2.
  3. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2013. URL: http://dx.doi.org/10.2200/S00520ED1V01Y201307DCT011.
  4. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1-20:45, 2016. URL: http://dx.doi.org/10.1145/2903137.
  5. Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier. Parameterized algorithms and hardness results for some graph motif problems. In Proc. 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008), pages 31-43. Springer, 2008. Google Scholar
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.03.003.
  7. Andreas Björklund, Petteri Kaski, Lukasz Kowalik, and Juho Lauri. Engineering motif search for large graphs. In Ulrik Brandes and David Eppstein, editors, Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015, pages 104-118. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.10.
  8. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. 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 43-56. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_4.
  9. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proc. ACM Symposium on Principles of Distributed Computing (PODC 2015), pages 143-152, 2015. Google Scholar
  10. Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci., 86(2):243-266, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90020-3.
  11. Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting - (extended abstract). In Marcos K. Aguilera, editor, Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, volume 7611 of Lecture Notes in Computer Science, pages 195-209. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33651-5_14.
  12. Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In Feasible Mathematics II, pages 219-244, 1994. URL: http://dx.doi.org/10.1007/978-1-4612-2566-9_7.
  13. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 367-376. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611493.
  14. P. Erdős, A. Hajnal, and J. W. Moon. A problem in graph theory. The American Mathematical Monthly, 71(10):1107-1110, 1964. URL: http://dx.doi.org/10.2307/2311408.
  15. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Dennis Olivetti Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three notes on distributed property testing. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), 2017. Google Scholar
  16. Guy Even, Reut Levi, and Moti Medina. Faster and simpler distributed algorithms for testing and correcting graph properties in the CONGEST-model, 2017. arXiv:1705.04898 [cs.DC]. Google Scholar
  17. Orr Fischer, Tzlil Gonen, and Rotem Oshman. Distributed property testing for subgraph-freeness revisited, 2017. arXiv:1705.04033 [cs.DS]. Google Scholar
  18. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 142-151, 2014. Google Scholar
  19. Pierre Fraigniaud, Pedro Montealegre, Dennis Olivetti, Ivan Rapaport, and Ioan Todinca. Distributed subgraph detection, 2017. arXiv:1706.03996 [cs.DC]. Google Scholar
  20. 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: http://dx.doi.org/10.1007/978-3-662-53426-7_25.
  21. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 381-389. ACM, 2017. URL: http://dx.doi.org/10.1145/3087801.3087811.
  22. Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST, 2017. arXiv:1705.10195 [cs.DC]. Google Scholar
  23. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, 2009. Google Scholar
  24. Burkhard Monien. How to find long paths efficiently. North-Holland Mathematics Studies, 109:239-254, 1985. Google Scholar
  25. Crispin Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, s1-39(1):12-12, 1964. URL: http://dx.doi.org/10.1112/jlms/s1-39.1.12.
  26. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. Tight bounds for distributed graph computations, 2016. arXiv:1602.08481 [cs.DC]. Google Scholar
  27. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2000. Google Scholar
  28. Oleg Pikhurko. A note on the Turán function of even cycles. Proceedings of the Americal Mathematical Society, 140:3687-3692, 2012. URL: http://dx.doi.org/10.1090/S0002-9939-2012-11274-2.
  29. Stefan Schmid and Jukka Suomela. Exploiting locality in distributed SDN control. In Nate Foster and Rob Sherwood, editors, Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN 2013, The Chinese University of Hong Kong, Hong Kong, China, Friday, August 16, 2013, pages 121-126. ACM, 2013. URL: http://dx.doi.org/10.1145/2491185.2491198.
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