Abstract

We present deterministic constant-round protocols for the graph connectivity problem in the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts a single sublinear size message to all other nodes. Communication rounds are synchronous. This model is sometimes called the broadcast congested clique. Specifically, we exhibit a deterministic protocol that computes the connected components of the input graph in [1/epsilon] rounds, each player communicating O(n(epsilon) . log n) bits per round, with 0 epsilon = 1. We also provide a deterministic one-round protocol for connectivity, in the model when each node receives as input the graph induced by the nodes at distance at most r > 0, and communicates O(n(1/r) . log n) bits. This result is based on a d-pruning protocol, which consists in successively removing nodes of degree at most d until obtaining a graph with minimum degree larger than d. Our technical novelty is the introduction of deterministic sparse linear sketches: a linear compression function that permits to recover sparse Boolean vectors deterministically.