Graph connectivity in log steps using label propagation

Abstract

The fastest deterministic algorithms for connected components take logarithmic time and perform superlinear work on a Parallel Random Access Machine (PRAM). These algorithms maintain a spanning forest by merging and compressing trees, which requires pointer-chasing operations that increase memory access latency and are limited to shared-memory systems. Many of these PRAM algorithms are also very complicated to implement. Another popular method is "leader-contraction" where the challenge is to select a constant fraction of leaders that are adjacent to a constant fraction of non-leaders with high probability. Instead we investigate label propagation because it is deterministic and does not rely on pointer-chasing. Label propagation exchanges representative labels within a component using simple graph traversal, but it is inherently difficult to complete in a sublinear number of steps. We are able to solve the problems with label propagation for graph connectivity. We introduce a surprisingly simple framework for deterministic graph connectivity using label propagation that is easily adaptable to many computational models. It propagates directed edges and alternates edge direction to achieve linear edge count each step and sublinear convergence. We present new algorithms in PRAM, Stream, and MapReduce for a simple, undirected graph $G=(V,E)$ with $n=|V|$ vertices, $m=|E|$ edges. Our approach takes $O(m)$ work each step, but we can only prove logarithmic convergence on a path graph. It was conjectured by Liu and Tarjan (2019) to take $O(\log n)$ steps or possibly $O(\log^2 n)$ steps. We leave the proof of convergence as an open problem.