Approximate Distance Sensitivity Oracles in Subquadratic Space

Abstract

An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\ddot{I}ƒ\ge 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a pair of vertices $s,t$ and a set $F$ of at most $f$ edges, it returns a $\ddot{I}ƒ$-approximation of the $s$-$t$-distance in $G-F$. We study $f$-DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for $\ddot{I}ƒ\ge 3$. We present, for any constant $f\ge 1$ and $\hat{I}\pm \in (0,\frac{1}{2})$, and any $\epsilon >0$, a randomized $f$-DSO with stretch $3+\epsilon$ that w.h.p. takes $\tilde{O}(n^{2-\frac{\hat{I}}{\pm }f+1})\cdot O(\log n/\epsilon {)}^{f+2}$ space and has an $O(n^{\hat{I}}\pm /{\epsilon }^2)$ query time. The time to build the oracle is $\tilde{O}(m{n}^{2-\frac{\hat{I}}{\pm }f+1})\cdot O(\log n/\epsilon {)}^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k-1$ that w.h.p. takes $O(D^{f+o(1)}{n}^{1+1/k})$ space and has $\tilde{O}(D^{o(1)})$ query time, with a preprocessing time of $O(D^{f+o(1)}m{n}^{1/k})$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1+\epsilon$ and preprocessing time $O(n^{5+o(1)}/{\epsilon }^f)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O(m{n}^{2+o(1)}/{\epsilon }^f)$.

The is the arXiv version of the eponymous paper that appeared first at STOC 2023 and then was extended to a journal version, published in TheoretiCS