New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the O( P 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 eO( p n). Despite extensive research over the years, the question of whether one can reduce the diameter to o( p n) with eO (n) shortcut edges has been left open. We provide the first improved diameter-sparsity tradeo for this problem, breaking the p n 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 eO(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 eO(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: S(n;D) = ( eO (n2=D3); for D n1=3; eO ((n=D)3=2); for D > n1=3 : We also extend our algorithms to provide improved ( ) hopsets for n-vertex weighted directed graphs.