Compact and Fast Sensitivity Oracles for Single-Source Distances

Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph
G with n vertices and m edges. In this paper we present two efficient single-source approximate-
distance sensitivity oracles, namely compact data structures which are able to quickly report
an approximate (by a multiplicative stretch factor) distance from s to any node of G following
the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n)
which is able to report 2-approximate distances from the source in O(1) time. Then, we further
develop our construction by building, for any 0 < ε < 1, another sensitivity oracle having size
O n · 1 ε log 1 ε , and is able to report a (1 + ε)-approximate distance from s to any vertex of G in
O log n · 1 ε log 1 ε time. Thus, this latter oracle is essentially optimal as far as size and stretch are
concerned, and it only asks for a logarithmic query time. Finally, our results are complemented
with a space lower bound for the related class of single-source additively-stretched sensitivity
oracles, which is helpful to realize the hardness of designing compact oracles of this type.