Paper Info
Title
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Abstract
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path distances.We provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. Math 2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts. <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a significant progress on the tantalizing open problem concerning the formal connection between hopsets and spanners, e.g., as posed by Elkin and Neiman [Bull. EATCS 2020].
Year
DOI
Venue
2022
10.1109/FOCS54457.2022.00078
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
ISSN
Hopsets,spanners,pairwise distance preservers,reachability
Conference
1523-8288
ISBN
Citations 
PageRank 
978-1-6654-5520-6
0
0.34
References 
Authors
30
2
Name
Order
Citations
PageRank
Shimon Kogan1676.60
Merav Parter216932.59