Improved Distance (Sensitivity) Oracles with Subquadratic Space

Abstract

A distance oracle (DO) with stretch $(\hat{I}\pm ,{\hat{I}}^2)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$, returns a value $\hat{d}(s,t)$ such that $d(s,t)\le \hat{d}(s,t)\le \hat{I}\pm \cdot d(s,t)+{\hat{I}}^2$. An $f$-edge fault-tolerant distance sensitivity oracle ($f$-DSO) additionally receives a set $F$ of up to $f$ edges and estimates the $s$-$t$-distance in $G-F$. Our first contribution is a new distance oracle with subquadratic space for undirected graphs. Introducing a small additive stretch ${\hat{I}}^2>0$ allows us to make the multiplicative stretch $\hat{I}\pm$ arbitrarily small. This sidesteps a known lower bound of $\hat{I}\pm \ge 3$ (for ${\hat{I}}^2=0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0,W]$ that, for any positive integer $t$ and any $c\in (0,\ell /2]$, has stretch $(1+\frac{1}{\ell },2W)$, space $\tilde{O}(n^{2-\frac{c}{t}})$, and query time $O(n^c)$. These are the first subquadratic-space DOs with $(1+\hat{I}\mu ,O(1))$-stretch generalizing Agarwal and Godfrey's results for sparse graphs [SODA 2013] to general undirected graphs. Our second contribution is a framework that turns a $(\hat{I}\pm ,{\hat{I}}^2)$-stretch DO for unweighted graphs into an $(\hat{I}\pm (1+\epsilon ),{\hat{I}}^2)$-stretch $f$-DSO with sensitivity $f=o(\log (n)/\log \log n)$ and retains subquadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [STOC 2023, TheoretiCS 2024] for the special case of stretch $(3,0)$ and $f=O(1)$. By combining the framework with our new distance oracle, we obtain an $f$-DSO that, for any ${\hat{I}}^3\in (0,(\ell +1)/2]$, has stretch $((1+\frac{1}{\ell })(1+\epsilon ),2)$, space $n^{2-\frac{\hat{I}}{³}(\ell +1)(f+1)+o(1)}/{\epsilon }^{f+2}$, and query time $\tilde{O}(n^3/{\epsilon }^2)$.

An extended abstract of this work appeared at FOCS 2024