2023/12/04 by Farhadi, Alireza, Liu, S. Cliff, Shi, Elaine
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.02332
Computing the connected components of a graph is a fundamental problem in algorithmic graph theory. A major question in this area is whether we can compute connected components in o(log n) parallel time. Recent works showed an affirmative answer in the Massively Parallel Computation (MPC) model for a wide class of graphs. Specifically, Behnezhad et al. (FOCS'19) showed that connected components can be computed in O(log d + log log n) rounds in the MPC model. More recently, Liu et al. (SPAA'20) showed that the same result can be achieved in the standard PRAM model but their result incurs Θ((m+n) ⋅ (log d + log log n)) work which is sub-optimal. In this paper, we show that for graphs that contain well-connected components, we can compute connected components on a PRAM in sub-logarithmic parallel time with optimal, i.e., O(m+n) total work. Specifically, our algorithm achieves O(log(1/λ) + log log n) parallel time with high probability, where λ is the minimum spectral gap of any connected component in the input graph. The algorithm requires no prior knowledge on λ. Additionally, based on the 2-Cycle Conjecture we provide a time lower bound of Ω(log(1/λ)) for solving connected components on a PRAM with O(m+n) total memory when λ≤ (1/log n)c, giving conditional optimality to the running time of our algorithm as a parameter of λ.