English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a graph $G$, a $D$-diameter-reducing exact hopset is a small set ofadditional edges $H$ that, when added to $G$, maintains its graph metric butguarantees that all node pairs have a shortest path in $G \cup H$ using at most$D$ edges. A shortcut set is the analogous concept for reachability. Theseobjects have been studied since the early '90s due to applications in parallel,distributed, dynamic, and streaming graph algorithms.  For most of their history, the state-of-the-art construction for eitherobject was a simple folklore algorithm, based on randomly sampling nodes to hitlong paths in the graph. However, recent breakthroughs of Kogan and Parter[SODA '22] and Bernstein and Wein [SODA '23] have finally improved over thefolklore diameter bound of $\widetilde{O}(n^{1/2})$ for shortcut sets and for$(1+\epsilon)$-approximate hopsets. For both objects it is now known that onecan use $O(n)$ hop-edges to reduce diameter to $\widetilde{O}(n^{1/3})$. Theonly setting where folklore sampling remains unimproved is for exact hopsets.Can these improvements be continued?  We settle this question negatively by constructing graphs on which any exacthopset of $O(n)$ edges has diameter $\widetilde{\Omega}(n^{1/2})$. Thisimproves on the previous lower bound of $\widetilde{\Omega}(n^{1/3})$ by Koganand Parter [FOCS '22]. Using similar ideas, we also polynomially improve thecurrent lower bounds for shortcut sets, constructing graphs on which anyshortcut set of $O(n)$ edges reduces diameter to $\widetilde{\Omega}(n^{1/4})$.This improves on the previous lower bound of $\Omega(n^{1/6})$ by Huang andPettie [SIAM J. Disc. Math. '18]. We also extend our constructions to providelower bounds against $O(p)$-size exact hopsets and shortcut sets for othervalues of $p$; in particular, we show that folklore sampling is near-optimalfor exact hopsets in the entire range of $p \in [1, n^2]$.

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier