New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier

For an n-vertex digraph G = (V, E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to 1 O( √ n). Despite extensive research over the years, the question of whether one can reduce the diameter to o( √ n) with O(n) shortcut edges has been left open.

We provide the first improved diameter-sparsity tradeoff for this problem, breaking the √ n diameter barrier. Specifically, we show an O(n ω )-time randomized algorithm 2 for computing a linear shortcut set that reduces the diameter of the digraph to O(n 1/3 ). This narrows the gap w.r.t the current diameter lower bound of Ω(n 1/6 ) by [Huang and Pettie, SWAT'18]. Moreover, we show that a diameter of O(n 1/2 ) can in fact be achieved with a sublinear number of O(n 3/4 ) shortcut edges. Formally, letting S(n, D) be the bound on the size of the shortcut set required in order to reduce the diameter of any n-vertex digraph to at most D, our algorithms yield:

We also extend our algorithms to provide improved (β, ) hopsets for n-vertex weighted directed graphs.

• This project is funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 949083). 1 The notation O(•) hides poly-logarithmic terms in n. 2 Where ω is the optimal matrix multiplication constant.