Parallel Connectivity

6^th October 2022, 16:00
Artur Czumaj
University of Warwick

Abstract

We study the parallel complexity of graph connectivity, one of the most basic and fundamental optimization problems on graphs. We will focus on the nowadays classical model of Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only O(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.

While it is not difficult to see that the problem can be solved in O(log n) MPC rounds, in a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O(log D + loglog n) rounds on an MPC with low local space determine all connected components of a graph. In this talk I will present the main ideas behind these algorithms and then show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O(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 presenting an almost matching lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture.

This is based on a joint work with Sam Coy that appeared at STOC’2022.