Closing the Gap Between Directed Hopsets and Shortcut Sets
share
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 tradeoff between the size of a shortcut set / hopset and the value of β. 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 (or a (β,ϵ)-hopset) with O(n) edges? Not only is this a natural structural question in its own right, but shortcuts sets / hopsets form the core of many distributed, parallel, and dynamic algorithms for reachability / shortest paths. 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 is to close the gap between shortcut sets and hopsets. That is, we show that for any graph G and any fixed ϵ there is a (Õ(n^1/3),ϵ) hopset with O(n) edges. More generally, we achieve a smooth tradeoff between hopset size and β which exactly matches the tradeoff of Kogan and Parter for shortcut sets (up to polylog factors). Using a very recent black-box reduction of Kogan and Parter, our new hopset implies improved bounds for approximate distance preservers.
READ FULL TEXT