Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
share
The success of massively parallel computation (MPC) paradigms such as MapReduce has led to a significant interest in better understanding their true computational power. The fundamental question in this regard is how the advantages of this model (e.g. free local computation) can be leveraged to improve the round-complexity of algorithms inherited from traditional parallel and distributed models such as PRAM or LOCAL. Problems such as maximal independent set (MIS) or maximal matching are among the most intensively studied problems in the field and logarithmic round algorithms have been known for these problems from 1980s. However, prior to our work, no sublogarithmic MPC algorithm was known for these problems using a truly sublinear space of n^1-Ω(1) per machine where n denotes the number of vertices. Our main result is a truly sublinear algorithm that takes O(α + ^2 n) rounds to compute MIS or maximal matching using an optimal total space of Õ(m) where m denotes the number of edges and α denotes the arboricity of the input graph. We believe parametrization by arboricity is particularly interesting for this regime of MPC since most families of sparse graphs have a small arboricity. Our algorithms do not assume arboricity is constant and do not require to be given α. This is the first substantial improvement over the known PRAM/LOCAL algorithms for these problems on such a wide class of graphs. Since trees have arboricity one, our algorithm improves and generalizes the recent algorithm of Brandt et al. [arXiv:1802.06748] that finds MIS on trees in O(^3 n) rounds. Moreover, the n-dependency of our algorithm exponentially improves over the corresponding O(α + √( n)) PRAM/LOCAL bounds by Barenboim et al. [FOCS'12] and Ghaffari [SODA'16].
READ FULL TEXT