Closing the Gap Between Directed Hopsets and Shortcut Sets

For an n-vertex directed graph G = (V, E), a β-shortcut set H is a set of additional edges H ⊆ V ×V such that G ∪ H has the same transitive closure as G, and for every pair u, v ∈ V , there is a uv-path in G ∪ H with at most β edges. A natural generalization of shortcut sets to distances is a (β, ε)-hopset H ⊆ V × V , where the requirement is that H and G ∪ H have the same shortest-path distances, and for every u, v ∈ V , there is a (1 + ε)-approximate shortest path in G ∪ H with at most β edges.

There is a large literature on the question of the tradeoff between the optimal size of a shortcut set / hopset and the value of β. In particular we highlight the most natural point on this tradeoff: what is the minimum value of β, such that for any graph G, there exists a β-shortcut set H with O(n) edges? Similarly, what is the minimum value of β such that there exists a (β, ϵ)-hopset with O(n) edges? Not only is this a very natural structural question in its own right, but shortcuts sets / hopsets form the core of a large number of distributed, parallel, and dynamic algorithms for reachability / shortest paths.

A lower bound of Hesse [SODA 2003] for directed graphs shows that if we restrict ourselves to hopsets with O(n) edges, the best we can guarantee is β = Ω(n 1/17 ) for both shortcut sets and hopsets [SODA 2003]; this was later improved to β = Ω(n 1/6 ) by Huang and Pettie [SWAT 2018]. Until very recently the best known upper bound was a folklore construction showing β = O(n 1/2 ), but in a breakthrough result Kogan and Parter [SODA 2022] improve this to β = Õ(n 1/3 ) for shortcut sets and Õ(n 2/5 ) for hopsets.

Our result in this paper is to close the gap between shortcut sets and hopsets introduced by the result of Kogan and Parter. That is, we show that for any graph G and any fixed ε there is a ( Õ(n 1/3 ), ε) hopset with O(n) edges. Our hopset improves upon the ( Õ(n 2/5 ), ε) hopset of Kogan and Parter. More generally, we achieve a smooth tradeoff between hopset size and β which exactly matches the tradeoff of Kogan and Parter for the simpler problem of shortcut sets (up to polylog factors).

Additionally, using a very recent black-box reduction of Kogan and Parter, our new hopset immediately implies improved bounds for approximate distance preservers.