Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond

Understand

We present $O(\log\log n)$ round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for constant coloring trees.

• Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as $n^{\delta}$ for any positive constant $\delta<1$.
• Our results improve over the $O(\log^2\log n)$ round algorithms of Behnezhad et al.
• [PODC'19].