Parallel Reachability in Almost Linear Work and Square Root Depth

Abstract

In this paper we provide a parallel algorithm that given any $n$-node $m$-edge directed graph and source vertex $s$ computes all vertices reachable from $s$ with $\tilde{O}(m)$ work and $n^{1/2+o(1)}$ depth with high probability in $n$ . This algorithm also computes a set of $\tilde{O}(n)$ edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most $n^{1/2+o(1)}$. Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman which had depth $\tilde{O}(n^{2/3})$. Further, we show how to leverage this algorithm to achieve improved distributed algorithms for single source reachability in the CONGEST model. In particular, we provide a distributed algorithm that given a $n$-node digraph of undirected hop-diameter $D$ solves the single source reachability problem with $\tilde{O}(n^{1/2}+n^{1/3+o(1)}{D}^{2/3})$ rounds of the communication in the CONGEST model with high probability in $n$. Our algorithm is nearly optimal whenever $D=O(n^{1/4-\epsilon })$ for any constant $\epsilon >0$ and is the first nearly optimal algorithm for general graphs whose diameter is $\Omega (n^{\delta })$ for any constant $\delta$.

38 pages. v2 fixes a small typo in Section 4 found by Aaron Bernstein. v3 fixes some overflow issues. v4 fixes the proof of Lemma 5.1. We thank Aaron Bernstein for pointing this out

Cited by in corpus (2)

• Minor Sparsifiers and the Distributed Laplacian Paradigm
• Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)