The Impact of Locality in the Broadcast Congested Clique Model

Abstract

The broadcast congested clique model (BClique) is a message-passing model of distributed computation where n 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 = \scrO (d \cdot log n). 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\leq 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 = \lfloor k/2\rfloor + 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 = \lfloor k/3\rfloor , then any one-round algorithm that solves Cycle>k needs the bandwidth b to be at least \Omega (n/ log n). We also show the existence of a one-round, deterministic BClique algorithm that solves Cycle\leq k with bandwitdh b = \scrO (n 1/\lfloor k/2\rfloor \cdot log n). On the negative side, we prove that, if \epsilon \leq 1/3 and 0 < r \leq k/4, then any \epsilon -error, R-round, b-bandwidth algorithm in the BClique[r] model that solves problem Cycle\leq k satisfies R \cdot b = \Omega (n 1/\lfloor k/2\rfloor).