Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)

Abstract

Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\ge 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 functions. A landmark PRDO due to Thorup and Zwick, with an improvement of Wulff-Nilsen, has $S(n,k)=O(k\cdot n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(\log k)$. The size of this oracle is $\hat{I}\text{c◯}(n\log n)$ for all $k$. Elkin and Pettie and Neiman and Shabat devised much sparser PRDOs, but their stretch was polynomially larger than the optimal $2k-1$. On the other hand, for non-path-reporting distance oracles, Chechik devised a result with $S(n,k)=O(n^{1+\frac{1}{k}})$, $f(k)=2k-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. We devise a PRDO with size $S(n,k)=O(\lceil \frac{k\log \log n}{\log n}\rceil \cdot n^{1+\frac{1}{k}})$, stretch $f(k)=O(k)$ and query time $q(k)=O(\log \lceil \frac{k\log \log n}{\log n}\rceil )$. We can also have size $O(n^{1+\frac{1}{k}})$, stretch $O(k\cdot \lceil \frac{k\log \log n}{\log n}\rceil )$ and query time $q(k)=O(\log \lceil \frac{k\log \log n}{\log n}\rceil )$. 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 $\hat{I}\mu >0$, any $k=1,2,...$, and any graph $G$ and a collection $\mathcal{P}$ of $p$ vertex pairs, there exists a $(1+\hat{I}\mu )$-approximate preserver with $O({\hat{I}}^3(\hat{I}\mu ,k)\cdot p+n\log k+n^{1+\frac{1}{k}})$ edges, where ${\hat{I}}^3(\hat{I}\mu ,k)=(\frac{\log k}{\hat{I}}\mu {)}^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter.

69 pages, 4 figures