2019/05/21 by Jambulapati, Arun, Liu, Yang P., Sidford, Aaron · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1905.08841
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 O(m) work and n1/2 + o(1) depth with high probability in n . This algorithm also computes a set of O(n) edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most n1/2 + o(1). Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman which had depth O(n2/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 O(n1/2 + n1/3 + o(1) D2/3) rounds of the communication in the CONGEST model with high probability in n. Our algorithm is nearly optimal whenever D = O(n1/4 - ε) for any constant ε> 0 and is the first nearly optimal algorithm for general graphs whose diameter is Ω(nδ) for any constant δ.