Fault-Tolerant ST-Diameter Oracles

Given two vertex sets S and T in a graph, the ST -diameter is the maximum s-t-distance between verticess ∈ S and t ∈ T .We study the problem of estimating the ST -diameter of graphs that are subject to a small number of transient edge failures. An f -edge faulttolerant ST -diameter oracle ( f -FDO-ST ) is a data structure that preprocesses a graph G, sets S, T , and a positive integer f . When queried with a set F of at most f failing edges, the oracle returns an estimate D of the ST -diameter in G − F. The oracle is said to have stretch σ $\geq$ 1 if diam(G−F, S, T ) $\leq$ D $\leq$ σ · diam(G−F, S, T ). We design new f -FDO-ST s by reducing their construction to that of all-pairs and singlesource distance sensitivity oracles ( f -DSOs). These are data structures that estimate the pairwise graph distances, or respectively the distances from a distinguished source, under up to f failures. We obtain several new trade-offs between the size of the ST- diameter oracles, their stretch guarantees, query and preprocessing times by combining our black-box reductions with f -DSO results from the literature. We further provide a lower bound on the space requirement of approximate ST-diameter oracles. ... mehrWe prove that there exists a family of graphs for which any f -FDO-ST with sensitivity f $\geq$ 2 and stretch better than 5/3 requires $\Omega$(n$^{3/2}$) bits of space, regardless of the query time.