Parallel Reachability in Almost Linear Work and Square Root Depth

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 Õ(m) work and n {1/2 + o(1) } depth with high probability in n. This algorithm also computes a set of Õ(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 [1] which had depth Õ(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 Õ(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-ε ) for any constant ε > 0 and is the first nearly optimal algorithm for general graphs whose diameter is Ω(n δ ) for any constant δ.

Authors

• Yang P. Liu
• Arun Jambulapati
• Aaron Sidford

Keywords

• Distributed algorithms
• Computational modeling
• Heuristic algorithms
• Parallel algorithms
• Directed graphs
• Complexity theory
• Optimization
• High Probability
• Undirected
• Directed Graph
• Linear Algorithm
• Distributed Algorithm
• Parallel Algorithm
• Path Length
• Parallelization
• Proof Of Theorem
• Shortest Path
• Low Depth
• First Search
• Pathfinding
• Algorithm For Problem
• Total Work
• Vertices
• Sequential Algorithm
• Probability 1
• Recursive Algorithm
• Linear Graph
• Breadth-first Search
• Communication Rounds
• Induced Subgraph
• Single Vertex
• Linear-time Algorithm
• Schwarz Inequality
• Constant Factor
• Original Graph
• Distributed Computing
• Parallel Computing
• Data Structures and Algorithms