Paper Info
Title
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Abstract
The approximate single-source shortest-path problem is as follows: given a graph with nonnegative edge weights and a designated source vertex s, return estimates of the distances from s to each other vertex such that the estimate falls between the true distance and (1+є) times the distance. This paper provides the first nearly work-efficient parallel algorithm with sublinear span (also called depth) for the approximate shortest-path problem on directed graphs. Specifically, for constant є and polynomially-bounded edge weights, our algorithm has work Õ(m) and span n1/2+o(1). Several algorithms were previously known for the case of undirected graphs, but none of the techniques seem to translate to the directed setting. The main technical contribution is the first nearly linear-work algorithm for constructing hopsets on directed graphs. A (β,є)-hopset is a set of weighted edges (sometimes called shortcuts) which, when added to the graph, admit β-hop paths with weight no more than (1+є) times the true shortest-path distances. There is a simple sequential algorithm that takes as input a directed graph and produces a linear-cardinality hopset with β=Õ(√n), but its running time is quite high—specifically Õ(m√n). Our algorithm is the first more efficient algorithm that produces a directed hopset with similar characteristics. Specifically, our sequential algorithm runs in Õ(m) time and constructs a hopset with Õ(n) edges and β = n1/2+o(1). A parallel version of the algorithm has work Õ(m) and span n1/2+o(1).
Year
DOI
Venue
2020
10.1145/3357713.3384270
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
ISSN
Parallel algorithm, hopsets, shortest paths, shortcuts
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-6979-4
1
0.35
References 
Authors
0
3
Name
Order
Citations
PageRank
Cao Nairen110.35
Jeremy T. Fineman258736.10
Russell Katina310.35