Given an undirected unweighted graph $G$ and a source set $S$ of $|S| = \sigma $ 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 \in S$ and $t \in V$. When $\sigma=n$, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with $\tilde O(n^2)$ space ($\tilde O(\cdot)$ hides poly $\log n$ 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 $\tilde O(\sigma^{1/2}n^{3/2})$ with the query time of $O(\sqrt{n\sigma})$ for the above problem. We improve their result by designing a data-structure of size $\tilde O(\sigma^{1/2} n^{3/2})$ that can answer queries in $\tilde 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(\sqrt{n\sigma})$. This eventually gives a bound of $O( n \sqrt{n \sigma}) = O(\sigma^{1/2}n^{3/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.?

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok