## New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier

by Shimon Kogan and Merav Parter

#### Oded's comments

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})$.

#### The original abstract

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.

Back to
list of Oded's choices.