Deterministic Massively Parallel Algorithms for Ruling Sets
share
In this paper we present a deterministic O(loglog n)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with Õ(n) memory; this algorithm also runs in O(loglog n) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the O(logΔ)-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).
READ FULL TEXT