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(\mathrm{log}D+\mathrm{log}\mathrm{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 $\mathrm{log}\mathrm{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(\mathrm{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
$\mathrm{\Omega}(\mathrm{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(\mathrm{log}D)$
rounds with a canonical deterministic algorithm, improving over the $O(\mathrm{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.

PREPRINT

# Optimal Deterministic Massively Parallel Connectivity on Forests

Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto

Submitted on 7 November 2022

## Abstract

## Preprint

Comment: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023

Subjects: Computer Science - Distributed, Parallel, and Cluster Computing; Computer Science - Data Structures and Algorithms