Faster algorithms improve distance tools for directed graphs
Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets
Data Structures and Algorithms
Summary
Figuring out shortest paths in directed networks can be slow and complex. The authors developed faster algorithms that improve three key tools used to understand distances in directed graphs. These tools are hopsets, shortcut sets, and distance preservers, all of which help computers quickly estimate or preserve important distance information. Their faster methods work well on both special and general graphs and improve the efficiency of these distance calculations.
What this means in practice
- •For network engineers: Accelerate routing and distance estimation processes by using faster hopset construction in directed network topologies.
- •For graph database developers: Speed up preprocessing steps that maintain accurate distance queries through improved shortcut and distance preserver algorithms.
Authors
Ben Bals, Daniel Dadush, Gary Hoppenworth, Yasamin Nazari, Rajath Rao K. N
Abstract
While there have been many recent advances in getting better tradeoffs for directed distance structures such as hopsets, shortcut sets and distance preservers, most known algorithms are inefficient. In this work we provide three results: - Faster algorithms for directed $(1+ε)$-hopsets, matching the state-of-the-art size/hopbound trade-offs of Bernstein & Wein [SODA23]. Our algorithm is first designed for DAGs and then extended to general graphs (up to $n^{o(1)}$ factors) using the recent DAG projection result of Haeupler, Jiang, and Saranurak [STOC26]. - Faster \textit{deterministic} algorithms for constructing shortcut sets, matching the state-of-the-art size/hopbound tradeoffs of Kogan & Parter [SODA22A]. - Using our improved directed hopset construction, we get significantly faster algorithms for computing source-wise distance preservers. This algorithm is based on speeding-up reductions of Kogan & Parter [SODA22B] by using certain structural properties of our hopsets.