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), respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.
-- 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 language | English |
|---|---|
| Title of host publication | 21st International Conference on Principles of Distributed Systems, OPODIS 2017 |
| Publisher | Schloss Dagstuhl-Leibniz-Zentrum für Informatik |
| Publication status | Published - 2017 |
| MoE publication type | A4 Article in a conference publication |
| Event | International Conference on Principles of Distributed Systems - Lisbon, Portugal Duration: 18 Dec 2017 → 20 Dec 2017 Conference number: 21 |
Publication series
| Name | Leibniz International Proceedings in Informatics |
|---|---|
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Volume | 95 |
| ISSN (Electronic) | 1868-8969 |
Conference
| Conference | International Conference on Principles of Distributed Systems |
|---|---|
| Abbreviated title | OPODIS |
| Country/Territory | Portugal |
| City | Lisbon |
| Period | 18/12/2017 → 20/12/2017 |