Abstract

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 (CYCLEk). 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