Optimal Deterministic Massively Parallel Connectivity on Forests
Preprint
Abstract
We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent breakthrough result by Coy and Czumaj [STOC'22] shows that, in this setting, it is possible to deterministically identify connected components on graphs in $O(\log D + \log\log n)$ rounds, where $D$ is the diameter of the graph and $n$ the number of nodes. The authors left open a major question: is it possible to get rid of the additive $\log\log n$ factor and deterministically identify connected components in a runtime that is completely independent of $n$? We answer the above question in the affirmative in the case of forests. We give an algorithm that identifies connected components in $O(\log D)$ deterministic rounds. The total memory required is $O(n+m)$ words, where $m$ is the number of edges in the input graph, which is optimal as it is only enough to store the input graph. We complement our upper bound results by showing that $\Omega(\log D)$ time is necessary even for component-unstable algorithms, conditioned on the widely believed 1 vs. 2 cycles conjecture. Our techniques also yield a deterministic forest-rooting algorithm with the same runtime and memory bounds. Furthermore, we consider Locally Checkable Labeling problems (LCLs), whose solution can be verified by checking the $O(1)$-radius neighborhood of each node. We show that any LCL problem on forests can be solved in $O(\log D)$ rounds with a canonical deterministic algorithm, improving over the $O(\log n)$ runtime of Brandt, Latypov and Uitto [DISC'21]. We also show that there is no algorithm that solves all LCL problems on trees asymptotically faster.
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Near-Optimal Massively Parallel Graph Connectivity2019
- Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds2019
- Breaking the Linear-Memory Barrier in $\mathsf {MPC}$: Fast $\mathsf {MIS}$ on Trees with Strongly Sublinear Memory2019
- Parallel Graph Connectivity in Log Diameter Rounds2018
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model2016
- A Model of Computation for MapReduce2010
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- Distributive graph algorithms Global solutions from local data1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986