2021/07/07 by Bilò, Davide, Cohen, Sarel, Friedrich, Tobias +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2107.03485
We design f-edge fault-tolerant diameter oracles (f-FDOs). We preprocess a given graph G on n vertices and m edges, and a positive integer f, to construct a data structure that, when queried with a set F of |F| ≤ f edges, returns the diameter of G-F. For a single failure (f=1) in an unweighted directed graph of diameter D, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+ε), constant query time, space O(m), and a combinatorial preprocessing time of \widetildeO(mn + n1.5 √(Dm/ε)).We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of \widetildeO(mn + n2/ε). The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of \widetildeO(n2.5794 + n2/ε). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. For multiple failures (f>1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f+2), query time O(f2log2n), \widetildeO(fn) space, and preprocessing time \widetildeO(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space. We show that for unweighted graphs with polylogarithmic diameter and up to f = o(log n/ loglog n) failures, one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn1+o(1), query time no(1), and space n2+o(1). When using fast matrix multiplication instead, the preprocessing time can be improved to nω+o(1), where ω< 2.373 is the matrix multiplication exponent.