The impact of locality in the broadcast congested clique model

The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where ra nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = 0(d - logra). Then, we introduce a new 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, denoted BCLIQUE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE<k) and the problem of detecting an induced cycle of length at least k + 1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = [k/2\ + 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 = [k/3], then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Q(ra/ logra). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE<fc with bandwitdh b =O(n1/[k/2] log n). On the negative side, we prove that, if e < 1/3 and 0 < r < fc/4, then any e-error, R-round, 6-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE<fc satisfies R-b =Ω(n1/ [k/2]).