Our input is an undirected weighted graph G = (V,E) on n vertices along with a source set S ⊆ V. The problem is to preprocess G and build a compact data structure such that upon query Qu(s,v,f) where (s,v) ∈ S×V and f is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the s-v distance in G-f. We use a fault-tolerant ST-distance oracle from the work of Bilò et al. (STACS 2018) to construct an S×V approximate distance oracle or sourcewise approximate distance oracle of size Õ(|S|n + n^{3/2}) with multiplicative stretch at most 5. We construct another fault-tolerant sourcewise approximate distance oracle of size Õ(|S|n + n^{4/3}) with multiplicative stretch at most 13. Both the oracles have O(1) query answering time.

We study the replacement paths problem in the CONGEST model of distributed computing. Given an s-t shortest path P, the goal is to compute, for every edge e in P, the shortest-path distance from s to t avoiding e. For unweighted directed graphs, we establish the tight randomized round complexity bound for this problem as [EQUATION] by showing matching upper and lower bounds. Our upper bound extends to (1 + ϵ)-approximation for weighted directed graphs. Our lower bound applies even to the second simple shortest path problem, which asks only for the smallest replacement path length. These results improve upon the very recent work of Manoharan and Ramachandran (SIROCCO 2024), who showed a lower bound of [EQUATION] and an upper bound of [EQUATION], where hst is the number of hops in the given s-t shortest path P.

We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set F of two edges, as well as a source node s and a destination node t, our oracle returns the length of the shortest path from s to t that avoids F in O(1) time with a high probability. The space complexity of our oracle is Õ(n²) , making it nearly optimal in terms of both space and query time. Prior to our work, Pettie and Duan [SODA 2009] designed a dual fault-tolerant distance oracle that required Õ(n²) space and O(log n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.

We present an f-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from [1 … W]. Given a set F of f edges, as well as a source node s and a destination node t, our oracle returns the shortest path from s to t avoiding F in O((cf log(nW))O(f2)) time, where c > 1 is a constant. The space complexity of our oracle is O(f4n2log2 (nW)). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).

In a graph G with a source s, we design a distance oracle that can answer the following query: Query(s,t,e) - find the length of shortest path from a fixed source s to any destination vertex t while avoiding any edge e. We design a deterministic algorithm that builds such an oracle in Õ(m √n) time. Our oracle uses Õ(n √n) space and can answer queries in Õ(1) time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in Õ(m √n+n²) time. Using our distance oracle, we also solve the single source replacement path problem (Ssrp problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the Ssrp problem. The running time of their algorithm is Õ(m √n + n²). In this paper, we show that the Ssrp problem can be solved in Õ(m √n + |ℛ|) time, where ℛ is the output set of the Ssrp problem in G. Our Ssrp algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of Ω(m √n) for any combinatorial algorithm that solves this problem.