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 (n^2-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 ( (n) / 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 n^ 2- { (+1) (f+1) + o (1) }/^f+2, and query time O (n^ /²).