Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in the recent breakthrough for the negative-length Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen [FOCS '22] extended the use of LDDs to directed graphs for the first time. Specifically, their LDD deletes each edge with probability at most O(1/D ⋅ log²n), while ensuring that each strongly connected component in the remaining graph has a (weak) diameter of at most D. In this work, we make further advancements in the study of directed LDDs. We reveal a natural and intuitive (in hindsight) connection to Expander Decompositions, and leveraging this connection along with additional techniques, we establish the existence of an LDD with an edge-cutting probability of O(1/D ⋅ log n log log n). This improves the previous bound by nearly a logarithmic factor and closely approaches the lower bound of Ω(1/D ⋅ log n). With significantly more technical effort, we also develop two efficient algorithms for computing our LDDs: a deterministic algorithm that runs in time Õ(m poly(D)) and a randomized algorithm that runs in near-linear time Õ(m). We believe that our work provides a solid conceptual and technical foundation for future research relying on directed LDDs, which will undoubtedly follow soon.

Abstract Locally Checkable Labeling () problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and colorings. A successful line of research has been studying the complexities of s on paths/cycles, trees, and general graphs, providing many interesting results for the model of distributed computing. In this work, we initiate the study of problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an problem in the model, automatically provides an exponentially faster algorithm for the low-space setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the setting are obtained through lower bounds for problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests this is not possible, hence using optimal memory requires new solutions.

Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures the central challenges in data center computations. Chang et al. [PODC'2019] gave an extremely fast, constant time, algorithm for the (Δ+1)-coloring problem, where Δ is the maximum degree of an input graph of n nodes. The algorithm works in the most restrictive low-space setting, where each machine has nδ local space for a constant 0 < δ < 1.

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 present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ < 1. Here D is the diameter of the tree and n is the number of nodes---we emphasize that our running time is independent of n.

We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log*n) rounds in forests (with high probability) and 2O(log*n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm.

We show the first conditionally optimal deterministic algorithm for $3$-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log \log n)$ rounds and uses optimal global space. The best previous algorithm requires $4$ colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an $O(\log \log n)$-round algorithm to compute a partition of the forest into $O(\log n)$ ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.

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(\log \log n)$ time (mid-complexity regime). We observe that obtaining a greater speed-up than from $n^{o(1)}$ to $Θ(\log \log n)$ is conditionally impossible, since the problem of 3-coloring trees, which is a LCL problem with LOCAL time complexity $n^{o(1)}$, has a conditional MPC lower bound of $Ω(\log \log n)$ [Linial, FOCS'87; Ghaffari, Kuhn and Uitto, FOCS'19]. We emphasize that we solve LCL problems on constant-degree trees, and that our algorithms are deterministic, component-stable, and work in the low-space MPC model, where local memory is $O(n^δ)$ for $δ\in (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 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.