Optimal Deterministic Massively Parallel Connectivity on Forests

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

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

38 Downloads (Pure)

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 Ω(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.
Original languageEnglish
Title of host publicationProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PublisherSociety for Industrial and Applied Mathematics
Pages2589-2631
Number of pages26
ISBN (Electronic)978-1-61197-755-4
DOIs
Publication statusPublished - 2023
MoE publication typeA4 Conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Florence, Italy
Duration: 22 Jan 202325 Jan 2023
Conference number: 34

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryItaly
CityFlorence
Period22/01/202325/01/2023

Fingerprint

Dive into the research topics of 'Optimal Deterministic Massively Parallel Connectivity on Forests'. Together they form a unique fingerprint.

Cite this