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 α ⩾ 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 ∈ (0, ℓ/2], has stretch (1+ 1 ℓ , 2W ), space O(n 2-c ℓ ), and query time O(n c ). These are the first subquadraticspace DOs with (1+ε, O(1))-stretch generalizing Agarwal and Godfrey's results for sparse graphs [SODA 2013] to general undirected graphs. We also construct alternative DOs with even smaller space at the cost of a higher additive stretch. For any integer k ⩾ 1, the DOs have a stretch (2k-1+ 1 ℓ , 4kW ), space O(n

), and query time O(n c ). Our second contribution is a framework that turns any (α, β)-stretch DO for unweighted graphs into an (α(1+ε), β)-stretch f -DSO with sensitivity f = o(log(n)/ log log n) and retains subquadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [STOC 2023, TheoretiCS 2024] for the special case of stretch (3, 0) and f = O(1). We also derandomize the entire construction. 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 n 2- γ (ℓ+1)(f +1) +o(1) /ε f +2 , and query time O(n γ /ε 2 ). This is the first deterministic f -DSO with subquadratic space, near-additive stretch, and sublinear query time.