Generic Single Edge Fault Tolerant Exact Distance Oracle

Abstract

Given an undirected unweighted graph G and a source set S of |S|=? sources, we want to build a data structure which can process the following query {\sc Q}(s,t,e): find the shortest distance from s to t avoiding an edge e, where s?S and t?V. When ?=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n2) space (O~(?) hides poly logn factor.) and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{\`o} et. al. (STACS 2018) designed a data-structure of size O~(?1/2n3/2) with the query time of O(n?????) for the above problem. We improve their result by designing a data-structure of size O~(?1/2n3/2) that can answer queries in O~(1) time. In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of the {\em replacement} paths ending at a vertex t are disjoint, then the number of such paths is O(n?????). This eventually gives a bound of O(nn?????)=O(?1/2n3/2) for their problem. {\em Disjointness of detours} is a very crucial property used in the above result. We show a similar result for a subset of replacement path which \textbf{may not} be disjoint. This result is the crux of our paper and may be of independent interest.?