Deterministic Massively Parallel Connectivity
Deterministic Massively Parallel Connectivity
复制标题
确定性大规模并行连接
DOI：
10.1137/22m1520177
复制
发表时间：
2023
影响因子：
1.6
通讯作者：
Coy S
中科院分区：
文献类型：
--
作者：
Coy S
本文研究了在大规模并行计算（MPC）模型上设计基本图算法的问题。该问题的输入是一个无向图G，它有n个顶点和n个中边，D是G中任何连通分支的最大直径。我们考虑的MPC具有低的局部空间，允许每台机器只存储Θ（nδ）个字，对于任意常数δ>0，并且具有线性的全局空间（即机器数量乘以本地可用空间），也就是说，具有最佳利用率。在最近的一项突破中，Andoni等人（FOCS'18）和Behnezhad等人（FOCS'19）设计了并行随机算法，（logD+ loglogn）轮在具有低局部空间的MPC上确定图的所有连通分量，改进了从早期PRAM算法的工作中导出的O（logn）的经典界。我们表明，渐近相同的界限也可以实现确定性算法：我们提出了一个确定性MPC低局部空间算法，在O（logD+ loglogn）轮确定连接组件的输入图。我们的结果匹配的复杂性，最先进的随机算法为这项任务。本文中提出的技术也可以应用到一些相关的问题中，为寻找生成森林、最小生成森林等问题提供了新的确定性MPC算法。我们通过扩展最近的一个以1-vs-2-cycle猜想为条件的MPC连通性下界来补充我们的上界（其中要求D ≥ log 1 +Ω（1）n），通过显示一个相关的条件硬度Ω（logD）MPC对D的整个谱进行舍入，覆盖了当D ≤O（logn）时一个特别有趣的范围。
We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graphGwithnvertices andmedges, and withDbeing the maximum diameter of any connected component inG. We consider the MPC withlow local space, allowing each machine to store only Θ(nδ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization.In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that inO(logD+ loglogn) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound ofO(logn) derived from earlier works on PRAM algorithms.In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that inO(logD+ loglogn) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc.We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requiresD≥ log1+Ω(1)n), by showing a related conditional hardness of Ω(logD) MPC rounds for the entire spectrum ofD, covering a particularly interesting range whenD≤O(logn).