Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty
Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.
An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch $k=2\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$. This trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $Ω(m)$ space. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u \to p_v \to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. We prove that every \emph{pivot-based} $1$-hop ADO with \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for graphs with constant degree. This matches the best known ADOs with $\tilde{O}(1)$ query time, at every known stretch, up to polylogarithmic factors. We also extend our lower bound to pivot-based ADOs with any constant number $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets and improved lower bounds for general $β$-hop hopsets.
Shiri Chechik, Gur Lifshitz, Avi Kadria, Liam Roditty
In this paper, we develop three new analytical tools for the Thorup-Zwick hierarchy: the Mixed-Level Growth, Two-Level Growth, and Long-Short Growth lemmas. Using these tools, we obtain improved approximate distance oracles (ADOs), and algorithms for $n$-pairs shortest paths ($n$-PSP), multiple-source shortest paths (MSSP), and $ST$-shortest paths, as well as new hopsets. One of our main results is a $(\frac 65 k+O(1))$-stretch ADO with $\tilde O(mn^{1/k})$ preprocessing time and space (where $\tilde O$ hides polylogarithmic factors), and $\tilde O(n^{1/k})$ query time, breaking, for sparse graphs, the $(2k-O(1))$-stretch barrier for ADOs with $\tilde O(n^{1+1/k})$ space and $\tilde O(n^{1/k})$ query time. In unweighted graphs, we also obtain a $(\frac 65 k+O(1),O(k))$-approximate ADO with $\tilde O(n^{1+1/k})$ space and $\tilde O(n^{1/k})$ query time. This also yields a $(\frac 65 k+O(1))$-approximation algorithm for $m$-pairs shortest paths ($m$-PSP) in $\tilde O(mn^{1/k})$ time, answering the question of Chechik, Hoch, and Lifshitz [SODA'25] of whether the $2k-O(1)$ barrier for $n$-PSP in $\tilde O(mn^{1/k})$ time can be broken. For unweighted graphs, we give a new analysis of the existing $\tilde O(mn^{1/k}+n^{1+2/k})$-time $n$-PSP algorithm of [Chechik et al., SODA'25], and show that, without any modification, it is a $(k,k-1)$-approximation, i.e., $d(u,v)\le\hat d(u,v)\le k\cdot d(u,v)+k-1$ for every queried pair. This improves its multiplicative factor from $\frac 43 k+O(1)$ to $k$, and the leading coefficient $k$ is tight for this algorithm. Moreover, for graphs with $m=Ω(n^{1+1/k})$, this answers the question of Dalirrooyfard et al. [FOCS'22] up to the additive $k-1$.