# Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths

Preprint · Nairen Cao, Jeremy T. Fineman, Katina Russell

- Archive id: arxiv:1912.05506
- Published: 2019-12-11
- arXiv: https://arxiv.org/abs/1912.05506
- Source URL: https://arxiv.org/abs/1912.05506
- PDF: https://arxiv.org/pdf/1912.05506
- Provenance: arxiv

## 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 \\emph{directed} graphs. Specifically, for constant $ε$ and polynomially-bounded edge weights, our algorithm has work $\\tilde{O}(m)$ and span $n^{1/2+o(1)}$. Several algorithms were previously known for the case of \\emph{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 $β=O(\\sqrt{n})$, but its running time is quite high---specifically $\\tilde{O}(m\\sqrt{n})$. Our algorithm is the first more efficient algorithm that produces a directed hopset with similar characteristics. Specifically, our sequential algorithm runs in $\\tilde{O}(m)$ time and constructs a hopset with $\\tilde{O}(n)$ edges and $β= n^{1/2+o(1)}$. A parallel version of the algorithm has work $\\tilde{O}(m)$ and span $n^{1/2+o(1)}$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.