Approximate Distance Sensitivity Oracles in Subquadratic Space

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 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 σ-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 σ ≥ 3. We present, for any constant f ≥ 1 and α ∈ (0, 1/2), and any ε > 0, a randomized f-DSO with stretch 3 + ε that w.h.p. takes O(n2-α/f+1) · O(log n/ε)ᶠ⁺² space and has an O(n^α/ε²) query time. The time to build the oracle is O(mn2-α/f+1) · O(log n/ε)ᶠ⁺¹. 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ᶠ⁺ᵒ⁽¹⁾ n1+1/k) space and has O(Dᵒ⁽¹⁾) query time, with a preprocessing time of O(Dᶠ⁺ᵒ⁽¹⁾ mn1/k). Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an f-DSO with stretch 1+ε and preprocessing time O(n⁵⁺ᵒ⁽¹⁾/εᶠ), albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O(mn²⁺ᵒ⁽¹⁾/εᶠ).