Deterministic Subgraph Detection in Broadcast CONGEST

Janne H. Korhonen, Joel Rybicki

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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), respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.
Original languageEnglish
Title of host publication21st International Conference on Principles of Distributed Systems, OPODIS 2017
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Principles of Distributed Systems - Lisbon, Portugal
Duration: 18 Dec 201720 Dec 2017
Conference number: 21

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN (Electronic)1868-8969


ConferenceInternational Conference on Principles of Distributed Systems
Abbreviated titleOPODIS

Cite this