Reading between the levels: new tools for the Thorup-Zwick hierarchy and their applications

Abstract

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{6}{5}k+O(1))$-stretch ADO with $\tilde{O}(m{n}^{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{6}{5}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{6}{5}k+O(1))$-approximation algorithm for $m$-pairs shortest paths ($m$-PSP) in $\tilde{O}(m{n}^{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}(m{n}^{1/k})$ time can be broken. For unweighted graphs, we give a new analysis of the existing $\tilde{O}(m{n}^{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{4}{3}k+O(1)$ to $k$, and the leading coefficient $k$ is tight for this algorithm. Moreover, for graphs with $m=\Omega (n^{1+1/k})$, this answers the question of Dalirrooyfard et al. [FOCS'22] up to the additive $k-1$.