Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. Unsatisfactorily, all current $\text{poly} (\log \log n)$-round MPC algorithms seem to get fundamentally stuck at the linear-memory barrier: their efficiency crucially relies on each machine having space at least linear in the number $n$ of nodes. As this might not only be prohibitively large, but also allows for easy if not trivial solutions for sparse graphs, we are interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, $n^δ$ for any $0<δ<1$. We devise a degree reduction technique that reduces maximal matching and maximal independent set in graphs with arboricity $λ$ to the corresponding problems in graphs with maximum degree $\text{poly}(λ)$ in $O(\log^2 \log n)$ rounds. This gives rise to $O\left(\log^2\log n + T(\text{poly} λ)\right)$-round algorithms, where $T(Δ)$ is the $Δ$-dependency in the round complexity of maximal matching and maximal independent set in graphs with maximum degree $Δ$. A concurrent work by Ghaffari and Uitto shows that $T(Δ)=O(\sqrt{\log Δ})$. For graphs with arboricity $λ=\text{poly}(\log n)$, this almost exponentially improves over Luby's $O(\log n)$-round PRAM algorithm [STOC'85, JALG'86], and constitutes the first $\text{poly} (\log \log n)$-round maximal matching algorithm in the low-memory MPC model, thus breaking the linear-memory barrier. Previously, the only known subpolylogarithmic algorithm, due to Lattanzi et al. [SPAA'11], required strongly superlinear, that is, $n^{1+Ω(1)}$, memory per machine.