Improved Distance (Sensitivity) Oracles with Subquadratic Space

A distance oracle (DO) with stretch (α, β) for a graph G is a data structure that, when queried with vertices s and t, returns a value d(s,t) such that d(s,t) ≤ d(s,t) ≤ α · d(s,t) + β. 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 β > 0 allows us to make the multiplicative stretch α arbitrarily small. This sidesteps a known lower bound of α ≥ 3 (for β = 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 ∈ (0, /2], has stretch (1+1/, 2W), space O(n2-c/t), and query time O(nᶜ). These are the first subquadratic-space DOs with (1+ε, 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 (α,β)-stretch DO for unweighted graphs into an (α (1+ε),β)-stretch f-DSO with sensitivity f = o(log(n)/loglog n) and retains subquadratic space. This generalizes a result by Bil\`o, 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 γ ∈ (0, (+1)/2], has stretch ((1+1/) (1+ε), 2), space n2- γ/(+1)(f+1) + o(1)/εᶠ⁺², and query time O(nγ /ε²).