Improved Distance (Sensitivity) Oracles with Subquadratic Space

A distance oracle (DO) for a graph G is a data structure that, when queried with vertices s,t, returns an estimate d(s,t) of their distance in G. The oracle has stretch (α, β) if the estimate satisfies 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 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 β > 0 allows one to make the multiplicative stretch α arbitrarily small. This sidesteps a known lower bound of α≥slant 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 ℓ and any c\in(0,ℓ/2], has stretch (1+1/ℓ,2W), space O(n2-c/ℓ), and query time O(nc), generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an (α,β)- stretch} DO for unweighted graphs into an (α(1+ϵ),β)-stretch}. f-DSO} with sensitivity f=o(log(n)/loglog 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-DSO that, for any γ(0, (ℓ+1)/2], has stretch ((1+1/ℓ)(1+ϵ), 2), space n2-γ(t+1)(f+1)}+o(1)/ϵf+2, and query time O(nγ/ϵ2). This is the first f-DSO} with subquadratic space, near-additive stretch, and sublinear query time.