Generic single edge fault tolerant exact distance oracle

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 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(n²) space¹ and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bilò et. al. (STACS 2018) designed a data-structure of size O(σ¹/²n³/²) with the query time of O(nσ) for the above problem. We improve their result by designing a data-structure of size O(σ¹/²n³/²) 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 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(σ¹/²n³/²) for their problem. 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 may not be disjoint. This result is the crux of our paper and may be of independent interest.