FOCS Conference 2023 Conference Paper
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)
- Michael Elkin
- Idan Shabat
Given an n-vertex undirected graph $G=(V, E, w)$ and a parameter $k \geq 1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n, k)$, that given a query $(u, v) \in V^{2}$, returns an $f(k)$-approximate shortest $u-v$ path P in G within time $q(k)+O(|P|)$. Here $S(n, k), f(k)$ and $q(k)$ are arbitrary (hopefully slowly-growing) functions. A distance oracle that only returns an approximate estimate $\hat{d}(u, v)$ of the distance $d_{G}(u, v)$ between the queried vertices is called a nonpath-reporting distance oracle. A landmark PRDO due to Thorup and Zwick [56] has $S(n, k)=O\left(k \cdot n^{1+\frac{1}{k}}\right), f(k)=2 k-1$ and $q(k)=O(k)$. Wulff-Nilsen [59] devised an improved query algorithm for this oracle with $q(k)=O(\log k)$. The size of this oracle is $\Omega(n \log n)$ for all k. Elkin and Pettie [30] devised a PRDO with $S(n, k)=O\left(\log k \cdot n^{1+\frac{1}{k}}\right), f(k)=O\left(k^{\log _{4 / 3} 7}\right)$ and $q(k)=O(\log k)$. Neiman and Shabat [46] recently devised an improved PRDO with $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=O\left(k^{\log _{4 / 3} 4}\right)$ and $q(k)=O(\log k)$. These oracles (of [30], [46]) can be much sparser than $O(n \log n)$ (the oracle of [46] can have linear size), but their stretch is polynomially larger than the optimal bound of $2 k-1$. On the other hand, a long line of non-pathreporting distance oracles culminated in a celebrated result by Chechik [14], in which $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=2 k-1$ and $q(k)=O(1)$. In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. In particular, we devise a PRDO with size $S(n, k)=$ $O\left(\left[\frac{k \cdot \log \log n}{\log n}\right] \cdot n^{1+\frac{1}{k}}\right)$, stretch $f(k)=O(k)$ and query time $q(k)=O\left(\log \left\lceil\frac{k \cdot \log \log n}{\log n}\right\rceil\right)$. As $\left\lceil\frac{k \cdot \log \log n}{\log n}\right\rceil=O(\log k)$ for $k \leq \log n$, its size is always at most $O\left(\log k \cdot n^{1+\frac{1}{k}}\right)$, and its query time is $O(\log \log k)$. Moreover, for $k=O\left(\frac{\log n}{\log \log n}\right)$, we have $\left[\frac{k \cdot \log \log n}{\log n}\right]=O(1)$, i. e. , $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=O(k)$, and $q(k)=O(1)$. For $k=\Theta(\log n)$, our oracle has size $O(n \log \log n)$, stretch $O(\log n)$ and query time $O\left(\log ^{(3)} n\right)$. We can also have linear size $O(n)$, stretch $O(\log n \cdot \log \log n)$ and query time $O\left(\log ^{(3)} n\right)$. These trade-offs exhibit polynomial improvement in stretch over the PRDOs of [30], [46]. For $k=\Omega\left(\frac{\log n}{\log \log n}\right)$, our tradeoffs also strictly improve the long-standing bounds of [56], [59]. Our results on PRDOs are based on novel constructions of approximate distance preservers, that we devise in this paper. Specifically, we show that for any $\epsilon gt 0$, any $k=1, 2, \ldots$, and any graph $G=(V, E, w)$ and a collection $\mathcal{P}$ of p vertex pairs, there exists a $(1+\epsilon)$-approximate preserver for $G, \mathcal{P}$ with $O\left(\gamma(\epsilon, k) \cdot p+n \log k+n^{1+\frac{1}{k}}\right)$ edges, where $\gamma(\epsilon, k)=$ $\left(\frac{\log k}{\epsilon}\right)^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter [41].