New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Õ(√n) 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 to1 . Despite extensive research over the years, the question of whether one can reduce the diameter to with Õ(n) shortcut edges has been left open. We provide the first improved diameter-sparsity tradeoff for this problem, breaking the diameter barrier. Specifically, we show an O(nω)-time randomized algorithm2 for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n1/3). This narrows the gap w.r.t the current diameter lower bound of Ω(n1/6) by [Huang and Pettie, SWAT'18]. Moreover, we show that a diameter of O(n1/2) can in fact be achieved with a sublinear number of O(n3/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.