Another breakthrough result presented at our theory seminar...
The general trade-off stated in the 2nd paragraph of the abstract asserts that for any diameter $d \geq n^{1/3}$ there exists a $d$-shortcut set of size $\tildeO((n/d)^{3/2})$, whereas for $d \leq n^{1/3}$ there exists a $d$-shortcut set of size $\tildeO(n^2/d^3)$. Furthermore, these shortcut sets can be found in polynomial-time.
In addition, for $d \geq n^{1/6}$, the paper demonstrate a lower bound of $\Omega((n/d)^{6/5})$ on the size of $d$-shortcut sets. For $d=n^{1/3}$ the bounds are $\Omega(n^{4/5})$ versus $\tildeO(n)$, whereas for $d=n^{1/2}$ they are $\Omega(n^{3/5})$ versus $\tildeO(n^{3/4})$.
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 \cup 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 $\widetilde{O}(\sqrt{n})$. Despite extensive research over the years, the question of whether one can reduce the diameter to $o(\sqrt{n})$ with $\widetilde{O}(n)$ shortcut edges has been left open.
In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the $\sqrt{n}$ diameter barrier. Specifically, we show an $O(n^{\omega})$-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to $\widetilde{O}(n^{1/3})$. We also extend our algorithms to provide improved $(\beta,\epsilon)$ hopsets for $n$-vertex weighted directed graphs.
Available from arxiv.