2024/08/19 by Bilò, Davide, Chechik, Shiri, Choudhary, Keerti +3 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2408.10014
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 \widehatd(s,t) such that d(s,t) ≤ \widehatd(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 \widetildeO(n2-(c)/(t)), and query time O(nc). 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(log(n)/loglog 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). 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- \fracγ(ℓ+1)(f+1) + o(1)/εf+2, and query time \widetildeO(nγ /ε2).