Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck · 2024
A distance oracle (DO) for a graph$G$is a data structure that, when queried with vertices$s,t$, returns an estimate$\widehat{d}(s,t)$of their distance in$G$. The oracle has stretch$(\alpha, \beta)$if the estimate satisfies$d(s,t)\leqslant \widehat{d}(s,t)\leqslant \alpha\cdot d(s,t)+\beta$. An$f-\mathbf{edge}$fault-tolerant distance sensitivity oracle$(f-\mathbf{DSO})$additionally receives a set$F$of up to$f$edges and estimates the distance in$G-F$. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch$\beta > 0$allows one to make the multiplicative stretch$\alpha$arbitrarily small. This sidesteps a known lower bound of$\alpha\geqslant 3$(for$\beta=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$\ell$and any$c\in(0,\ell/2]$, has stretch$(1+\frac{1}{\ell},2W)$, space$\widetilde{O}(n^{2-\frac{c}{\ell}})$, and query time$O(n^{c})$, generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an$(\alpha,\beta)- \mathbf{stretch}$DO for unweighted graphs into an$(\alpha(1+\varepsilon),\beta)-\mathbf{stretch}. f-\mathbf{DSO}$with sensitivity$f=o(\log(n)/\log\log n)$retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an$f-\mathbf{DSO}$that, for any$\gamma\in(0, (\ell+1)/2]$, has stretch$((1+\frac{1}{\ell})(1+\varepsilon), 2)$, space$n^{2-\frac{\gamma}{(t+1)(f+1)}+o(1)}/\varepsilon^{f+2}$, and query time$\widetilde{O}(n^{\gamma}/\varepsilon^{2})$. This is the first$f-\mathbf{DSO}$with subquadratic space, near-additive stretch, and sublinear query time.