Projects per year
Abstract
We show fast deterministic algorithms for
fundamental problems on forests in the challenging lowspace regime of
the wellknown 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
componentunstable algorithms, conditioned on the widely believed 1 vs. 2
cycles conjecture. Our techniques also yield a deterministic
forestrooting 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 language  English 

Title of host publication  Proceedings of the 2023 Annual ACMSIAM Symposium on Discrete Algorithms (SODA) 
Publisher  Society for Industrial and Applied Mathematics 
Pages  25892631 
Number of pages  26 
ISBN (Electronic)  9781611977554 
DOIs  
Publication status  Published  2023 
MoE publication type  A4 Conference publication 
Event  ACMSIAM Symposium on Discrete Algorithms  Florence, Italy Duration: 22 Jan 2023 → 25 Jan 2023 Conference number: 34 
Conference
Conference  ACMSIAM Symposium on Discrete Algorithms 

Abbreviated title  SODA 
Country/Territory  Italy 
City  Florence 
Period  22/01/2023 → 25/01/2023 
Fingerprint
Dive into the research topics of 'Optimal Deterministic Massively Parallel Connectivity on Forests'. Together they form a unique fingerprint.Projects
 1 Active

: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J. (Principal investigator), Cambus, M. (Project Member), Latypov, R. (Project Member) & Pai, S. (Project Member)
01/09/2020 → 27/04/2025
Project: Academy of Finland: Other research funding