Seminar Details

For an $n$-vertex digraph $G=(V,E)$, a emph{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.

Joint work with Shimon Kogan.