Gupta, ManojManojGuptaSingh, AditiAditiSingh2025-08-302025-08-302018-07-01[9783959770767]10.4230/LIPIcs.ICALP.2018.722-s2.0-85049775901https://d8.irins.org/handle/IITG2025/22819Given 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.falseData-structures | Distance oracles | Fault tolerant algorithms | Graph algorithmsConference Paper1 July 2018972cpConference Proceeding