New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the √(n) Barrier
share
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 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 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: S(n,D)=O(n^2/D^3), for D≤ n^1/3, O((n/D)^3/2), for D> n^1/3 . We also extend our algorithms to provide improved (β,ϵ) hopsets for n-vertex weighted directed graphs.
READ FULL TEXT