Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
share
In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method that solves most locally checkable labeling (LCL) problems exponentially faster in the low-space MPC model than in the LOCAL message passing model. In particular, we show that all solvable LCL problems on trees can be solved in O(log n) time (high-complexity regime) and that all LCL problems on trees with deterministic complexity n^o(1) in the LOCAL model can be solved in O(loglog n) time (mid-complexity regime). We emphasize that we solve LCL problems on constant-degree trees, our algorithms are deterministic and they work in the low-space MPC model, where local memory is O(n^δ) for δ∈ (0,1) and global memory is O(m). For the high-complexity regime, there are two key ingredients. One is a novel O(log n)-time tree rooting algorithm, which may be of independent interest. The other ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL problem on trees in O(log n) time. For the mid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical LOCAL algorithm for solving LCL problems on trees. For the special case of 3-coloring trees, which is a natural LCL problem with LOCAL time complexity n^o(1), we show that our analysis is (conditionally) tight, as it matches the conditional Ω(loglog n)-time lower bound for component-stable algorithms.
READ FULL TEXT