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, 12), and any > 0, a randomized f-DSO with stretch 3 + that w. h. p. takes O (n^2-{f+1}) O (n/) ^f+2 space and has an O (n^/²) query time. The time to build the oracle is O (mn^2-{f+1}) O (n/) ^f+1. 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^f+o (1) n^1+1/k) space and has O (D^o (1) ) query time, with a preprocessing time of O (D^f+o (1) mn^1/k). Chechik, Cohen, Fiat, and Kaplan SODA 2017 devised an f-DSO with stretch 1+ and preprocessing time O (n^5+o (1) /ᶠ), albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O (mn^2+o (1) /ᶠ).