Abstract | dc.description.abstract | The broadcast congested clique model is a message-passing
model of distributed computation where n nodes communicate with each
other in synchronous rounds. The joint input to the n nodes is an undirected graph G on the same set of nodes, with each node receiving the list
of its immediate neighbors in G. In each round each node sends the same
message to all other nodes, depending on its own input, on the messages
it has received so far, and on a public sequence of random bits. One parameter of this model is an upper bound b on the size of the messages,
also known as bandwidth. In this paper we introduce another parameter
to the model. We study the situation where the nodes, initially, instead
of knowing their immediate neighbors, know their neighborhood up to a
fixed radius r.
In this new framework we study one of the hardest problems in
distributed graph algorithms, this is, the problem of detecting, in G,
an induced cycle of length at most k (Cycle≤k) and the problem of
detecting in G an induced cycle of length at least k + 1 (Cycle>k).
For r = 1, we exhibit a deterministic, one-round algorithm for solving
Cycle≤k with b = O(n
2/k log n) if k is even, and b = O(n
2/(k−1) log n) if
k is odd. We also prove, assuming the Erd˝os Girth Conjecture, that this
result is tight for k ≥ 4, up to logarithmic factors. More precisely, if each
node, instead of being able to see only its immediate neighbors, is allowed
to see up to distance r = bk/4c, and if we also allowed randomization and
multiple rounds, then the number of rounds R needed to solve Cycle≤k
must be such that R · b = Ω(n
2/k) if k is even, and R · b = Ω(n
2/(k−1))
if k is odd.
On the other hand, we show that, if each node is allowed to see up
to distance r = bk/2c + 1, then a polylogarithmic bandwidth is sufficient
for solving Cycle>k with only two rounds. Nevertheless, if nodes were
allowed to see up to distance r = bk/3c, then any one-round algorithm
that solves Cycle>k needs the bandwidth b to be at least Ω(n/ log n). | |