Simplified and Faster Algorithms for the Directed Single/Dual-Failure Replacement Paths via Modulo-Layer Hitting Sets

Introduction

In the replacement paths problem, we study how shortest paths change under edge failure. Specifically, given an unweighted directed graph $G=(V,E)$ with $n$ vertices and $m$ edges and two vertices $s,t \in V$, the classical replacement paths (RP) problem asks to compute, for every edge $e \in E$, a shortest $s$-$t$ path that avoids $e$. Its natural two-failure extension, the dual-failure replacement paths (2-FRP) problem, asks to compute, for every pair of edges $e,e' \in E$, a shortest $s$-$t$ path that avoids both $e$ and $e'$.

The replacement paths problem has been extensively studied in the literature [31, 33, 26, 19, 18, 42, 5, 16, 41, 39, 44, 30, 21, 10 VWX22, 11, 32, 8, 35, 22], motivated in part by its role as a basic model for fault-tolerant routing. In real-world networks, links may become unavailable due to failures, and it is desirable to quickly find alternative routes while preserving shortest-path guarantees. Replacement paths naturally capture this task by computing shortest routes that remain available after such failures. Beyond this networking motivation, replacement paths are also closely connected to several fundamental problems. In particular, replacement paths arise in computing Vickrey pricing for shortest paths in algorithmic mechanism design (see [34, 25]). They are also closely related to the $k$ shortest paths problem, which is itself a classical and well-studied problem [29, 17].

For the classical RP problem, the complexity differs significantly between undirected and directed graphs. Note that the output size of RP is only $\Theta(n)$, since it suffices to consider failures of edges on a fixed shortest $s$–$t$ path. For undirected graphs, RP can be solved essentially as efficiently as single-source shortest paths [31, 30]. In contrast, RP on directed graphs appears substantially harder. For unweighted directed graphs, Roditty and Zwick [39] gave a randomized combinatorial algorithm running in $\tilde{O}(m\sqrt{n})$ time. Obtaining a deterministic algorithm with a comparable running time remained open for more than a decade, until Alon, Chechik, and Cohen [1] gave a deterministic $\tilde{O}(m\sqrt{n})$-time combinatorial algorithm. This running time is optimal up to $n^{o(1)}$ factor among combinatorial algorithms, assuming the combinatorial Boolean Matrix Multiplication (BMM) conjecture [43]. For weighted directed graphs, RP is subcubic-equivalent to APSP [43].³ For algebraic algorithms, Vassilevska Williams [41] gave a randomized $\tilde{O}(Mn^\omega)$-time algorithm⁴ for edge weights in $\{-M,\ldots,M\}$.

Although the notion of a “combinatorial algorithm” is not formally defined, here and throughout we use the term informally to refer to algorithms that do not rely on fast matrix multiplication, such as Strassen-like methods. Such algorithms are often viewed as more efficient in practice, since fast matrix multiplication algorithms typically involve large hidden constants. We refer the reader to [3 Section 1.1] for a more extensive discussion of the motivations for seeking combinatorial algorithms, as well as for possible operational definitions of this notion.

The 2-FRP problem is considerably less understood. Vassilevska Williams, Woldeghebriel, and Xu [VWX22] gave a $\tilde{O}(n^3)$-time algorithm for weighted directed graphs and an $n^{8/3-o(1)}$ conditional lower bound for combinatorial algorithms on unweighted directed graphs. Chechik and Zhang [11] subsequently gave the first truly subcubic combinatorial algorithm for unweighted directed graphs, with running time $\tilde{O}(n^{3-1/18})$. For algebraic algorithms, they also obtained a $\tilde{O}(Mn^{2.8716})$-time algorithm for edge weights in $\{-M,\ldots,M\}$. Thus, for combinatorial algorithms on unweighted directed graphs, there remains a substantial gap between the known upper and lower bounds. In contrast, for undirected graphs, Nogler and Vassilevska Williams [35] recently reduced 2-FRP to single source replacement paths, yielding a $\tilde{O}(m\sqrt{n}+n^2)$-time algorithm for unweighted graphs. They left open whether a similar reduction, possibly in a weaker form, can be obtained for directed graphs. We note that, although 2-FRP considers all pairs of failed edges, its output size is only $\Theta(n^2)$; see § 2.2 for details.

Our Results

Table 1 summarizes the best known upper and lower bounds for RP and 2-FRP, together with our new results. Our first result is a simple deterministic algorithm for the RP problem.

The running time in Theorem 1 is optimal up to an $n^{o(1)}$ factor among combinatorial algorithms [43], and removes the logarithmic overhead in the previous randomized and deterministic algorithms [39, 1].

More importantly, our derandomization is considerably simpler. The randomized algorithm of Roditty and Zwick [39] is conceptually simple, whereas its derandomization by Alon, Chechik, and Cohen [1] requires substantially more machinery, including the construction of critical paths using decremental shortest-path techniques and a greedy hitting-set procedure. To obtain a simpler deterministic algorithm, we introduce a new technique, which we call a modulo-layer hitting set. The idea is extremely simple. After performing BFS from $s$, we partition the vertices into $L = \Theta(\sqrt{n})$ classes according to their distances from $s$ modulo $L$, and use a smallest class, which has size at most $n/L = O(\sqrt{n})$, as the hitting set. We believe that the resulting algorithm is simple enough for textbook presentation and practical implementation.

Combined with the reduction of Roditty and Zwick [39], Theorem 1 also yields an efficient algorithm for computing the $k$ shortest simple $s$–$t$ paths.

Roditty and Zwick [39] reduced the $k$ simple shortest paths problem to $O(k)$ instances of the replacement paths problem. Thus, Corollary 2 follows from Theorem 1 without any logarithmic overhead.

Our second result is a faster combinatorial algorithm for the 2-FRP problem. Our algorithm builds on our new modulo-layer hitting-set technique introduced for RP and combines it with additional ideas.

Our algorithm improves the previous combinatorial bound $\widetilde{O}(n^{3-1/18})$ and is simpler than the previous algorithm of Chechik and Zhang [11]. Our algorithm also reduces directed 2-FRP to a collection of multiple-source replacement paths (MSRP) instances. This reduction can be viewed as a partial answer to the question of Nogler and Vassilevska Williams [35]. We then solve the resulting MSRP instances using the recent algorithm of Harada and Izumi [22] for directed graphs.

Our results demonstrate that our new modulo-layer hitting-set technique is useful for both directed RP and 2-FRP. We believe that this simple technique may also find applications to other related shortest-path problems.

Additional Related Work

Fast algorithms for replacement paths have also been studied on special graph classes, including planar graphs [18, 42] and surface embedded graphs [16]. Another line of work considers fast approximation algorithms [5, 12]. The replacement paths problem has been studied in distributed settings [32, 8].

A closely related line of work studies distance sensitivity oracles (DSOs), which can be viewed as a data-structure version of replacement paths. After preprocessing a graph, a DSO answers shortest-path distance queries efficiently under edge or vertex failures. DSOs have also been extensively studied in the literature [6, 21 CC20, 20, 38, 15, 28, 14, 23].

Direction	Weights	Det./Rand.	Upper Bound	Lower Bound
Replacement Paths (RP)
undir.	$[1,n^c]$	det.	$O(m+n\log n)$ [31]	$\Omega(m+n)$
dir.	$[1,n^c]$	det.	APSP-time [43]	$\Omega(m+n)$
dir.	$[-M,M]$	rand.	$\widetilde{O}(Mn^\omega)$ [41]	$\Omega(m+n)$
undir.	unweigh.	det.	$O(m+n)$ [30]	$\Omega(m+n)$
dir.	unweigh.	det.	$O(m\sqrt{n})$ [Theorem 1]	$mn^{1/2-o(1)}$† [43]
Dual-Failure Replacement Paths (2-FRP)
undir.	$[1,n^c]$	det.	APSP-time [35]	APSP-time [24, 9]
dir.	$[1,n^c]$	det.	$\widetilde{O}(n^3)$ [VWX22]	APSP-time [43]
undir.	$[1,M]$	rand.	$\widetilde{O}(Mn^\omega)$ [35]	$\Omega(n^2)$
dir.	$[-M,M]$	rand.	$\widetilde{O}(Mn^{2.8716})$ [11]	$\Omega(n^2)$
undir.	unweigh.	det.	$\widetilde{O}(m\sqrt{n}+n^2)$ [35]	$mn^{1/2-o(1)}$† [35]
dir.	unweigh.	rand.	$\widetilde{O}(n^{3-1/4})$ [Theorem 3]	$n^{8/3-o(1)}$† [VWX22]

Preliminaries

Notation

Let $G=(V,E)$ be a directed graph with $n=|V|$ vertices and $m=|E|$ edges. For an edge set $F\subseteq E$, we write $G\setminus F$ for the graph obtained from $G$ by removing all edges in $F$. For an edge $e\in E$, we simply write $G\setminus e$ instead of $G\setminus\{e\}$. For a directed graph $D$, let $D^{\mathrm{rev}}$ denote the graph obtained by reversing every edge of $D$. For a vertex subset $V'\subseteq V(D)$, let $D[V']$ denote the subgraph of $D$ induced by $V'$.

For a directed graph $D$, possibly with edge weights, and vertices $u,v$, we denote by $\operatorname{dist}_D(u,v)$ the length of a shortest $u$–$v$ path in $D$, or its minimum total weight when $D$ is weighted. We set $\operatorname{dist}_D(u,v)=\infty$ if $u\notin V(D)$, $v\notin V(D)$, or $D$ contains no $u$–$v$ path.

For a directed path or walk $\rho$ in $G$, we denote its vertex set and edge set by $V(\rho)$ and $E(\rho)$, respectively. We let $|\rho|$ denote the number of edges in $\rho$. For any $u,v\in V(\rho)$ where $u$ comes before $v$ on $\rho$, we write $\rho[u,v]$ for the subpath of $\rho$ from $u$ to $v$, and $\operatorname{dist}_{\rho}(u,v)$ for the length of this subpath. For two directed paths or walks $\alpha$ and $\beta$ such that the last vertex of $\alpha$ is the first vertex of $\beta$, we denote their concatenation by $\alpha\circ\beta$.

Throughout the paper, let $\pi=\langle v_0,v_1,\ldots,v_k\rangle$ be a fixed shortest path in $G$ from $s=v_0$ to $t=v_k$, and let $H:=G\setminus E(\pi)$. For a path $\tau$, let $H+\tau$ denote the graph obtained from $H$ by adding all edges of $\tau$.

For integers $a,b$ and a positive integer $L$, we write $a\equiv b\pmod{L}$ if $L$ divides $a-b$.

Replacement Paths and Variants

(Single-Failure) Replacement Paths (RP). Given a directed graph $G$, two vertices $s,t$, and a shortest $s$–$t$ path $\pi$, the replacement paths (RP) problem asks to compute $\operatorname{dist}_{G\setminus e}(s,t)$ for every edge $e\in E$. It suffices to consider edges on $\pi$, since removing an edge outside $\pi$ does not change the $s$–$t$ distance. Since $\pi$ contains at most $n-1$ edges, the output size of RP is $O(n)$.

Dual-Failure Replacement Paths (2-FRP). The dual-failure replacement paths (2-FRP) problem extends RP to two edge failures. The goal is to compute $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ for every pair of edges $e,e' \in E$.

Although there are $O(m^2)$ possible pairs of failed edges, the output size of 2-FRP is only $O(n^2)$. Indeed, it suffices to consider $e \in E(\pi)$ and, for each such edge $e$, only the edges $e'$ on a shortest $s$–$t$ path in $G \setminus e$. All other distances are equal to either $\operatorname{dist}_{G}(s,t)$ or $\operatorname{dist}_{G\setminus e}(s,t)$. Thus, only $O(n^2)$ nontrivial output values need to be represented.

Multiple Source Replacement Paths

In the multiple source replacement paths (MSRP) problem, we are given a graph and a set $S$ of $\sigma$ sources. For every source $u \in S$, a shortest-path tree $T_u$ rooted at $u$ is fixed, and the output consists of the distances $\operatorname{dist}_{G\setminus e}(u,v)$ for all $v$ and all edges $e$ on the tree path $T_u[u,v]$. For $e \notin E(T_u[u,v])$ the tree path survives, so $\operatorname{dist}_{G\setminus e}(u,v)=\operatorname{dist}_{G}(u,v)$. The case $\sigma=1$ is the single source replacement paths SSRP problem.

2-FRP for Weighted Directed Graphs

Our 2-FRP algorithm reduces groups of failure pairs to small weighted instances, on which we run the algorithm of Vassilevska Williams, Woldeghebriel, and Xu [VWX22] as a black box. They proposed algorithms for 2-FRP on an $n$-vertex directed graph with integer edge weights and no negative cycles in $O(n^3\log^2 n)$ time deterministically, or in $O(n^3\log n)$ time with high probability.

Canonical Replacement Paths

We use the notion of a canonical replacement path introduced in [VWX22]; see also [11], Definition 3 in the conference version.

Throughout the paper, in both the single-failure and dual-failure settings, whenever we consider a shortest replacement path, we choose it to be canonical. Such a canonical shortest replacement path always exists. Indeed, among all shortest $s$–$t$ paths in $G \setminus F$, choose $\rho$ minimizing $|E(\rho)\setminus E(\pi)|$. If $\rho$ is not canonical, then for some violating pair $u,v$, replacing $\rho[u,v]$ by $\pi[u,v]$ yields another shortest $s$–$t$ path with fewer edges outside $\pi$, which contradicts the choice of $\rho$.

Basic Fact on Single-Failure Replacement Paths

For two vertices $v_a,v_b \in V(\pi)$ with $a<b$, we call a shortest $v_a$–$v_b$ path in $H$ a detour. A standard structural fact about single-failure replacement paths is that a shortest replacement path can be decomposed into a prefix of $\pi$, followed by a single detour, and then a suffix of $\pi$; see, e.g., [10 Lemma 5]. See Figure 1 for an illustration. This gives the following identity, which forms the basis of fast algorithms for single-failure replacement paths.

Our New Simple Deterministic Algorithm for RP

We first introduce our new derandomization technique for the RP problem, which we call a modulo-layer hitting set. The same technique will later be applied to the 2-FRP problem.

By Lemma 7, a central task in designing fast RP algorithms is to efficiently compute the detour distances $\operatorname{dist}_{H}(v_a,v_b)$ for pairs of vertices $v_a,v_b \in V(\pi)$. Since there can be $\Theta(n^2)$ such pairs, these distances are usually not computed explicitly. Instead, they are computed implicitly. We first briefly review how previous algorithms handle these detours, and then describe our approach based on the modulo-layer hitting-set technique.

Previous randomized approach [39]. The randomized algorithm of Roditty and Zwick [39] is conceptually simple. It distinguishes replacement paths whose detour has at most $\lceil\sqrt{n}\rceil$ edges from those whose detour has more than $\lceil\sqrt{n}\rceil$ edges. Short detours are found deterministically. For long detours, a set $\mathcal{R}$ of pivots is chosen by including every vertex independently with probability $c\log n/\sqrt{n}$ for a sufficiently large constant $c$, and the distances in $H$ between the vertices of $\pi$ are computed by a BFS in each direction from every pivot. Since a long detour has more than $\lceil\sqrt{n}\rceil$ vertices, with high probability every long detour contains a pivot. Consequently, for every long detour from $v_a$ to $v_b$, we have $\operatorname{dist}_{H}(v_a,v_b)=\min_{r\in\mathcal{R}}\{\operatorname{dist}_{H}(v_a,r)+\operatorname{dist}_{H}(r,v_b)\}$.

Previous deterministic approach [1]. Derandomizing the pivot-selection step above is substantially more technically challenging. Alon, Chechik, and Cohen [1] obtained the first deterministic $O(m\sqrt{n}\log n)$-time algorithm. Their proof and algorithm require constructing a carefully chosen family of $O(n)$ critical paths, each path containing $\lceil\sqrt{n}\rceil$ edges. Computing this family efficiently requires a variant of the decremental single-source shortest-path algorithm of King [27]. They then apply a greedy hitting-set procedure to the family of critical paths, obtaining a set of $O(\sqrt{n}\log n)$ pivots that hits every critical path. These pivots are subsequently used within the framework of Roditty and Zwick [39]. The logarithmic factors in the size of the hitting set and in its computation account for the $\tilde{O}(\cdot)$ in the running time.

Overview of our approach. Our underlying idea is entirely different, and both the algorithm and its analysis are remarkably simple. The key difference is that we do not classify detours by their length, as in [39, 1]; instead, we classify them by whether they pass through the hitting set or stay within a small range of consecutive BFS layers from $s$, which we call a block (defined below).

Instead of constructing a hitting set for a carefully chosen family of critical paths, we obtain one directly from a single BFS from $s$. We group the vertices by their distance from $s$ modulo a parameter $L = \Theta(\sqrt{n})$, and let $\mathcal{R}$ consist of the vertices in a smallest group, which has size at most $n/L = O(\sqrt{n})$. In other words, for some $0 \le\ell^\star< L$, $\mathcal{R}$ is the union of the BFS layers at distances $h_q := \ell^\star+ qL$ from $s$ ($q \ge0$), where the BFS layer at distance $d$ is the set of vertices at distance exactly $d$ from $s$; we call these layers the separator layers. A block consists of two consecutive separator layers and all layers between them, i.e., the vertices at distances $h_{q-1}, h_{q-1} + 1, \ldots, h_q$ from $s$ for some $q \ge0$; see Figure 2 for an illustration.

Since $\operatorname{dist}_G(s,y) \le\operatorname{dist}_G(s,x) + 1$ for every edge $(x,y)$ of $G$, the following holds for every $q \ge0$: any path in a subgraph of $G$ that starts at a vertex at distance less than $h_q$ from $s$ and ends at a vertex at distance at least $h_q$ must contain a vertex at distance exactly $h_q$, i.e., a vertex of the separator layer at distance $h_q$, which belongs to $\mathcal{R}$. In fact, the same structural property is what lets the technique carry over to the 2-FRP problem, where the graph in which detours are sought changes with the second failure (§ 4).

Using this structural property, we show that every detour either visits a separator layer, i.e., contains a vertex of $\mathcal{R}$, or stays inside a single block. Thus, $\mathcal{R}$ serves as a hitting set for all detours that leave their block. Accordingly, the detour distances can be evaluated using two kinds of BFSs: detours of the former kind are handled by BFSs from and to every vertex of $\mathcal{R}$ in $H$, which take $O((m+n)n/L)$ time in total, and detours of the latter kind by BFSs inside each block from the vertices of $\pi$ in it, which take $O((m+n)L)$ time in total.

Since neither the size of this hitting set nor its construction involves a logarithmic factor, our algorithm runs in $O(m\sqrt{n})$ time, improving the $O(m\sqrt{n}\log n)$ bound of [1].

Modulo-Layer Hitting Set and Modulo-Layer Decomposition

Throughout, we fix a shortest $s$–$t$ path $\pi$ in $G$. Fix an integer parameter $1 \le L \le n$, whose value will be chosen later; we will eventually set $L := \lceil\sqrt{n}\rceil$. For $i \ge0$, the layer $i$ is the set $\Lambda_i := \{x \in V \mid\operatorname{dist}_G(s,x) = i\}$ of vertices at distance exactly $i$ from $s$. For $0 \le\ell< L$, let

Choose $\ell^\star\in\arg\min_{\ell} |\mathcal{R}_{\ell}|$ and put $\mathcal{R} := \mathcal{R}_{\ell^\star}$. Then $|\mathcal{R}| \le n/L$. We call the layers $h_q := \ell^\star+ qL$ ($q \ge0$), which are exactly the layers containing the vertices of $\mathcal{R}$, the separator layers. The separator layers divide the set of vertices reachable from $s$ into blocks: with the convention $h_{-1} := 0$, for $q \ge0$, block $q$ is $V_q := \{x \in V \mid h_{q-1} \le\operatorname{dist}_G(s,x) \le h_q\}$, and we let $H_q := H[V_q]$. Recall that $H := G \setminus E(\pi)$. That is, $V_0$ consists of the vertices of layers $0,\ldots,\ell^\star$ and, for $q \ge1$, $V_q$ consists of the vertices of the $L+1$ consecutive layers $h_{q-1},\ldots,h_q$, from one separator layer to the next, inclusive. Two consecutive blocks $V_q$ and $V_{q+1}$ share exactly the separator layer $h_q$ (i.e., $V_q \cap V_{q+1} = \Lambda_{h_q}$), and any two non-consecutive blocks are disjoint. Consequently, every vertex lies in at most two blocks (in exactly two if and only if it belongs to $\mathcal{R}$), and every edge of $H$ lies in at most two of the graphs $H_q$. Finally, for $q \ge0$, let $\gamma_q$ be the subpath of $\pi$ induced by $V_q$; that is, $\gamma_q = \pi[h_{q-1},\min\{h_q,k\}]$. Algorithm 1 summarizes this construction and Figure 2 illustrates it.

Since a vertex of $\pi$ on a separator layer belongs to two blocks, we fix the following convention. For $0 \le a \le k$, let $q(a)$ denote the unique index $q \ge0$ with $h_{q-1} \le a < h_q$. Explicitly, $q(a) = 0 if $a < \ell^\star$, and $q(a) = \lfloor(a-\ell^\star)/L\rfloor+ 1$ otherwise. Equivalently, for $a < k$, $q(a)$ is the index of the unique block containing the edge $e_a = (v_a,v_{a+1})$ of $\pi$, that is, $e_a \in E(\gamma_{q(a)})$. We always have $v_a \in V_{q(a)}$. If $v_a \in R$, then $v_a$ also lies in $V_{q(a)-1}$, and $q(a)$ selects the block in which $v_a$ is on the lower separator layer $h_{q(a)-1}$. Note that $a \leq a'$ implies $q(a) \leq q(a')$.

Algorithm 1: Modulo-Layer Hitting Set and Modulo-Layer Decomposition.

1 $\ell^\star\gets\arg\min_{0\leq\ell<L} |\{x \in V \mid\operatorname{dist}_G(s,x) \equiv\ell\pmod{L}\}|$

2 $R \gets\{x \in V \mid\operatorname{dist}_G(s,x) \equiv\ell^\star\pmod{L}\}$

3 $h_{-1} \gets0$ and $h_q \gets\ell^\star+ qL$ for $q \geq0$

4 $\gamma_q \gets\pi[h_{q-1},\min\{h_q,k\}]$ for every $q \geq0$

5 $V_q \gets\{x \in V \mid h_{q-1} \leq\operatorname{dist}_G(s,x) \leq h_q\}$ and $H_q \gets H[V_q]$ for every $q \geq0$ with $V_q \ne\varnothing$

Our algorithm computes the detour distances $\operatorname{dist}_H(v_a,v_b)$ using the following lemma. Recall that $\operatorname{dist}_{H_q}(v_a,v_b) = \infty$ whenever $v_a \notin V_q$ or $v_b \notin V_q$.

Proof. Every finite term on the right is the length of a walk from $v_a$ to $v_b$ in $H$. Hence, the right-hand side is at least $\operatorname{dist}_H(v_a,v_b)$.

For the converse inequality, we may assume that $\operatorname{dist}_H(v_a,v_b) < \infty$. Let $\tau$ be a shortest $v_a$–$v_b$ path in $H$. If $\tau$ contains a vertex $r^\star\in R$ (possibly $r^\star= v_a$ or $r^\star= v_b$), then $\operatorname{dist}_H(v_a,r^\star) + \operatorname{dist}_H(r^\star,v_b) = |\tau[v_a,r^\star]| + |\tau[r^\star,v_b]| = |\tau| = \operatorname{dist}_H(v_a,v_b)$. Otherwise, no vertex of $\tau$ lies on a separator layer, and we claim that every vertex $x$ of $\tau$ satisfies $h_{q-1} < \operatorname{dist}_G(s,x) < h_q$. Indeed, $\tau$ starts at $v_a$ with $a < h_q$; if some vertex of $\tau$ had layer at least $h_q$, then $\tau$ would contain a vertex of layer exactly $h_q$, which is a separator layer. Similarly, $\tau$ ends at $v_b$ with $b > h_{q-1}$; if some vertex of $\tau$ had layer less than $h_{q-1}$, $\tau$ would contain a vertex of layer exactly $h_{q-1}$, which is a separator layer. Thus, all vertices of $\tau$ belong to $V_q$, and since $H_q$ is the subgraph of $H$ induced by $V_q$, the path $\tau$ lies in $H_q$. Therefore $\operatorname{dist}_{H_q}(v_a,v_b) \leq|\tau| = \operatorname{dist}_H(v_a,v_b)$. □

By Lemma 8, every detour either visits a separator layer or stays inside one block, so the distance tables of Algorithm 2 suffice to evaluate the minimum in Lemma 7. Note that the detour distances $\operatorname{dist}_H(v_a,v_b)$ are never computed explicitly: the minimum is evaluated for all failed edges at once by prefix and suffix minima along $\pi$. The BFSs from and to all pivots $r \in R$ cost $O((m+n)n/L)$ time since $|R| \le n/L$, and the BFSs inside the blocks cost $O((m+n)L)$ time since each $\gamma_q$ has at most $L+1$ vertices and every vertex and every edge of $H$ lies in at most two of the graphs $H_q$. Choosing $L=\lceil\sqrt{n}\rceil$ yields Theorem 1.

Algorithm 2: Preprocessing distance computation

1. $\operatorname{dist}_H(r,*) \leftarrow\operatorname{BFS}(H,r)$ for each $r \in R$

2. $\operatorname{dist}_H(*,r) \leftarrow\operatorname{BFS}(H_{\mathrm{rev}},r)$ for each $r \in R$

3. $\operatorname{dist}_{H_q}(v,*) \leftarrow\operatorname{BFS}(H_q,v)$ for each $0 \le q$ and each $v \in V(\gamma_q)$

Overall Algorithm and Its Running Time.

Overall algorithm. Consider an edge $e_i=(v_i,v_{i+1}) \in E(\pi)$. Substituting Lemma 7 into Lemma 8 splits the minimum over $0 \le a \le i < b \le k$ into two candidates. The first one, the pivot candidate, collects the detours that pass through a vertex of $R$:

The second one, the block candidate, collects the detours that stay inside the block $V_{q(i)}$ containing $v_i$:

Note that, for $a \le i < b$, the term $\operatorname{dist}_{H_{q(a)}}(v_a,v_b)$ in Lemma 8 is finite only if $v_b \in V_{q(a)}$, and then $q(a)=q(i)=q(b)$ because every block consists of consecutive layers. Hence we obtain

and it remains to compute all values $C_i$ and $S_i$.

Algorithm 3 gives the pseudocode of our algorithm. The pivot candidates are computed from the tables $A_i(r)$ and $B_i(r)$, which a prefix and a suffix scan along $\pi$ build for each pivot $r$. The block candidates are computed in the same manner. For a block $V_q$ and a vertex $v_a \in V(\gamma_q)$, a suffix scan along $\gamma_q$ builds the table

and then $S_i=\min_{h_{q(i)}-1\le a\le i}\{a+W_{q(i),a}(i)\}$, since $v_a \in V_{q(i)}$ with $a \le i$ means $h_{q(i)}-1 \le a \le i$, and $v_b \in V_{q(i)}$ with $b>i$ means $i<b\le\min\{h_{q(i)},k\}$.

Running time. Algorithms 1 and 2 take $O(m)$ time and $O(mL+mn/L)$ time, respectively. For the pivot candidates, each of the $|R| \le n/L$ pivots performs two scans of $\pi$, each in $O(k)=O(n)$ time, which is $O(n^2/L)$ in total. For the block candidates, each block contains at most $L+1$ vertices of $\pi$ and is processed in $O(L^2)$ time; since $\pi$ meets at most $k/L+1=O(n/L)$ blocks, this is $O(nL)$ in total. Therefore, the total running time is $O(mn/L+mL+n^2/L+nL)$. By choosing $L=\lceil\sqrt{n}\rceil$, we obtain $O(m\sqrt{n})$ time, which proves Theorem 1.

Algorithm 3: The deterministic algorithm for RP.
Input: An unweighted directed graph $G=(V,E)$$ and vertices $s,t\in V$.
Output: $\operatorname{dist}_{G\setminus e_i}(s,t)$ for every edge $e_i=(v_i,v_{i+1})$ of $\pi$.
1  $L\leftarrow\lceil\sqrt{n}\rceil$, and run Algorithms 1 and 2
// Pivot candidates $C_i$
2  foreach $r\in\mathcal{R}$ do
3  $A\leftarrow\infty$
4  for $i\leftarrow 0$ to $k-1$ do
5  $A\leftarrow\min\{A,\ i+\operatorname{dist}_{H}(v_i,r)\}$
6  $A_i(r)\leftarrow A$
7  $B\leftarrow\infty$
8  for $i\leftarrow k-1$ downto $0$ do
9  $B\leftarrow\min\{B,\ \operatorname{dist}_{H}(r,v_{i+1})+k-(i+1)\}$
10 $B_i(r)\leftarrow B$
11 $C_i\leftarrow\min_{r\in\mathcal{R}}\{A_i(r)+B_i(r)\}$ for all $0\leq i<k$
// Block candidates $S_i$
12 foreach block $V_q$ do
13 foreach $v_a\in V(\gamma_q)$ do
14 $W\leftarrow\infty$
15 for $i\leftarrow\min\{h_q,k\}-1$ downto $a$ do
16 $W\leftarrow\min\{W,\ \operatorname{dist}_{H_q}(v_a,v_{i+1})+k-(i+1)\}$
17 $W_{q,a}(i)\leftarrow W$
18 $S_i\leftarrow\min_{h_q-1\leq a\leq i}\{a+W_{q,a}(i)\}$ for all $i$ with $q(i)=q$
19 return $\min\{C_i,S_i\}$ for all $0\leq i<k$

Our Improved Combinatorial Algorithm for 2-FRP

In this section, we present our improved combinatorial algorithm for the 2-FRP problem.

We divide the cases into two based on the position of the two failed edges $e,e'$ as follows:

1. One failure on $\pi$: $e\in E(\pi), e'\notin E(\pi)$

2. Both failures on $\pi$: $e,e'\in E(\pi)$

The first case is discussed in § 4.1, and the second case in Section 4.2. In both cases, we use the modulo-layer hitting set and the modulo-layer decomposition (§ 3.1), which is the key to making our algorithm faster and simpler than that of Chechik and Zhang [11].

Note that we do not consider the case of $e,e'\notin E(\pi)$ because $\pi$ is the shortest in this situation. Also, in the first case, we only consider $e'$ on the shortest $s$–$t$ path in $G\setminus e$. More precisely, for $e\in E(\pi)$, let $\rho_e$ be a fixed shortest $s$–$t$ path in $G\setminus e$, that is, a replacement path for $e$. Then, we consider $e'\in E(\rho_e)\setminus E(\pi)$.

One Failure on $\pi$

In the previous work by Chechik and Zhang [11], the running time in this case is $\widetilde{O}(n^{3-1/18})$. In this paper, we give an algorithm in $\widetilde{O}(mn^{3/4}+n^{5/2})$ time for this case.

Throughout this subsection, we set $L=\lceil\sqrt{n}\rceil$. Our algorithm for this case has two ingredients: the layer structure of § 3 and the recent combinatorial algorithm of Harada and Izumi [22] for multiple source replacement paths (MSRP) problem.

We can use the modulo-layer hitting set and the modulo-layer decomposition (§ 3.1) without any change. Roughly speaking, since $e' \notin E(\pi)$, the only difference from the single-failure setting is that we need to search for detours in $H\setminus e'$ instead of $H$. This change affects neither the layer structure nor its key property, since the separator layers, $\mathcal{R}$, and the blocks $V_q$ depend only on the distances from $s$ in $G$, and $\operatorname{dist}_G(s,y)\leq\operatorname{dist}_G(s,x)+1$ holds for every edge $(x,y)$ of $H\setminus e'$. Hence, for every $e'$ and every $0\leq a<b\leq k$, every $v_a$–$v_b$ path in $H\setminus e'$ either contains a vertex of $\mathcal{R}$ or lies entirely in $H_{q(a)}\setminus e'$. In other words, we do not need to construct a hitting set separately for each failure $e'\notin E(\pi)$; the single set $\mathcal{R}$ serves as a hitting set for all of them simultaneously. This allows us to avoid the extensive case analysis of Chechik and Zhang [11], which makes our algorithm for this case considerably simpler than theirs.

Formally, Lemmas 7 and 8 hold verbatim with $H$ and $H_q$ replaced by $H\setminus e'$ and $H_q\setminus e'$, as stated below.

Proof of Lemmas 10 and 11. The two lemmas are the counterparts of Lemmas 7 and 8 with $H$ replaced by $H\setminus e'$, and their proofs are almost identical to those given there; we therefore only indicate the differences and omit the details. For Lemma 10, the subpaths of $\pi$ avoid $e'$ because $e'\notin E(\pi)$, and the middle part of a shortest $s$–$t$ path in $G\setminus\{e,e'\}$ between its last vertex $v_a$ with $a\leq i$ and its first vertex $v_b$ with $b>i$ lies in $H\setminus e'$, since it has no internal vertex on $\pi$ and avoids $e'$. For Lemma 11, a shortest $v_a$–$v_b$ path in $H\setminus e'$ is in particular a path of $H$, so the argument on layers applies verbatim; its subpaths are shortest paths in $H\setminus e'$, and when all of its vertices lie in $V_q$, it is a path of $H_q\setminus e'$.

By Lemmas 10 and 11, all values $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ with $e\in E(\pi)$ and $e'\notin E(\pi)$ are determined by the distances $\operatorname{dist}_{H\setminus e'}(r,*)$ and $\operatorname{dist}_{H\setminus e'}(*,r)$ for $r\in\mathcal{R}$ and $\operatorname{dist}_{H_q\setminus e'}(v_i,*)$ for $v_i\in V_q$, over all $e'$. To compute these three distances, we solve the instance of the multiple source replacement paths (MSRP) problem of § 2.3, for which Harada and Izumi [22] give a combinatorial $\widetilde{O}(m\sqrt{\sigma n}+\sigma n^2)$-time algorithm with $\sigma$ sources (Lemma 4). Each of the three families above is exactly the output of one MSRP instance: for a graph $G'$ and a set $S$ of sources, MSRP$(G',S)$ returns $\operatorname{dist}_{G'\setminus e'}(u,x)$ for every $u\in S$, every vertex $x$, and every edge $e'$ of $G'$ (for $e'$ off the fixed shortest-path tree of $u$, the distance is $\operatorname{dist}_{G'}(u,x)$). Algorithm 4 is therefore the counterpart of Algorithm 2 in which every BFS is replaced by an MSRP computation. The sources of the first two instances are the $|\mathcal{R}|\leq n/L$ vertices of $\mathcal{R}$, and the instance for a block $V_q$ has at most $L+1$ sources, so by Lemma 4 the total time is $\widetilde{O}(mn/\sqrt{L}+n^3/L)$ for lines 1 and 2 and $\widetilde{O}(m\sqrt{Ln}+Ln^2)$ for line 3. Choosing $L=\lceil\sqrt{n}\rceil$ gives $\widetilde{O}(mn^{3/4}+n^{5/2})$, which is the bound of Lemma 9.

Algorithm 4: Preprocessing distance computation with one failure off $\pi$

1. $\operatorname{dist}_{H\setminus e'}(r,\ast) \gets\operatorname{MSRP}(H,\mathcal{R})$ for each $r \in\mathcal{R}$ and each $e' \in E(H)$

2. $\operatorname{dist}_{H\setminus e'}(\ast,r) \gets\operatorname{MSRP}(H^{\mathrm{rev}},\mathcal{R})$ for each $r \in\mathcal{R}$ and each $e' \in E(H)$

3. $\operatorname{dist}_{H_q\setminus e'}(v,\ast) \gets\operatorname{MSRP}(H_q,V(\gamma_q))$ for each $q \ge0$, $v \in V(\gamma_q)$, and $e' \in E(H_q)$

Once these distances are available, the overall algorithm is the same as that of § 3: for each failed edge $e \in E(\pi)$, the value $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ is the minimum of a pivot candidate and a block candidate, both of which are evaluated by prefix and suffix minima along $\pi$. The only difference is in the treatment of the second failed edge $e'$, which lies off $\pi$: the two candidates are defined with the distances in $H \setminus e'$ and $H_q \setminus e'$ in place of those in $H$ and $H_q$, and they are evaluated for every $e' \in E(\rho_e) \setminus E(\pi)$. The overall algorithm and its running time are described in Section A.

Both Failures on

In the previous work by Chechik and Zhang [11], the running time in this case is $\widetilde{O}(n^{3-1/7})$. In this paper, we propose an algorithm in $\widetilde{O}(n^{11/4})$ time for this case.

In this case, we also use the modulo-layer hitting set and the modulo-layer decomposition (§ 3.1) without any change. As in § 3 and Algorithm 1, we partition $\pi$ into consecutive blocks $\gamma_0,\gamma_1,\ldots$. These blocks form a partition of $E(\pi)$, each block has length $O(L)$, and there are $O(n/L)$ blocks in total. Throughout this subsection, we set $L = \lceil n^{3/4}\rceil$.

For each pair of failed edges, we consider the blocks that contain the two failures. For $e \in E(\gamma_p)$ and $e' \in E(\gamma_q)$ with $p \le q$, we distinguish whether the two failed edges lie in the same block or in different blocks, and handle the two cases separately. The former case ($p=q$) is discussed in § 4.2.1, and the latter case ($p<q$) in § 4.2.2.

Rough overview of the case where both failures lie on $\pi$. For edge pairs in the same block, we construct for each block an auxiliary weighted directed graph with $O(L)$ vertices and solve 2-FRP on this graph using Lemma 5. Since there are $O(n/L)$ blocks and each instance can be solved in $\widetilde{O}(L^3)$ time, the total time for this computation is $\widetilde{O}(nL^2)=\widetilde{O}(n^{5/2})$. For edge pairs in different blocks, we reduce the problem to $O(n/L)=O(n^{1/4})$ SSRP computations, which take $\widetilde{O}(n^{3-1/4})$ time in total.

Edge Pairs in the Same Block

We consider two failures $e,e' \in E(\pi)$ that lie on the same block, that is, $e_i,e_j \in E(\gamma_q)$ for some $q$. Our approach builds a weighted kernel on the vertex set $V(\gamma_q)\cup\{s',t'\}$, where $s'$ and $t'$ are two new vertices, so that $K_q$ has at most $L+3$ vertices and $\operatorname{dist}_{K_q\setminus\{e,e'\}}(s',t')=\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ for every pair $e,e' \in E(\gamma_q)$.

Kernel construction. The kernel $K_q$ is obtained by adding the following weighted edges (see Figure 3):

Type 1: every edge of $\gamma_q$ of weight 1

Type 2: an edge $(s',v)$ of weight $\operatorname{dist}_{G\setminus E(\gamma_q)}(s,v)$ for each $v \in V(\gamma_q)$

Type 3: an edge $(v,t')$ of weight $\operatorname{dist}_{G\setminus E(\gamma_q)}(v,t)$ for each $v \in V(\gamma_q)$

Type 4: an edge $(v_a,v_b)$ of weight $\operatorname{dist}_{H}(v_a,v_b)$ for each $v_a,v_b \in V(\gamma_q)$

Type 5: an edge $(s',t')$ of weight $\operatorname{dist}_{G\setminus E(\gamma_q)}(s,t)$

Edges of infinite weight are omitted, and an edge of Type 4 is kept distinct from a parallel edge of $\gamma_q$. The following lemma shows that the kernel is correct.

Proof. Every edge of $K_q \setminus\{e,e'\}$ expands to a walk of the same length in $G \setminus\{e,e'\}$. Therefore, $\operatorname{dist}_{K_q\setminus\{e,e'\}}(s',t')$ is at least $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$.

For the converse inequality, let $\rho$ be a canonical shortest $s$–$t$ path of $G \setminus\{e,e'\}$ with respect to $\pi$ and $\{e,e'\}$ (Definition 6). It suffices to find an $s'$–$t'$ walk of $K_q \setminus\{e,e'\}$ of length at most $|\rho|$. If $\rho$ uses no edge of $\gamma_q$, then $\rho$ is a path of $G \setminus E(\gamma_q)$, and the edge $(s',t')$ of Type 5 has weight at most $|\rho|$.

Otherwise, let $(v_i,v_{i+1})$ and $(v'_{i},v'_{i+1})$ be the first and the last edge of $\gamma_q$ on $\rho$, and split $\rho$ into the prefix $\rho[s,v_i]$, the middle part $\rho[v_i,v'_{i+1}]$, and the suffix $\rho[v'_{i+1},t]$. The prefix and the suffix use no edge of $\gamma_q$, so they are paths of $G \setminus E(\gamma_q)$, and their lengths are at least the weights of the edge $(s',v_i)$ of Type 2 and the edge $(v'_{i+1},t')$ of Type 3, respectively. Since $\rho$ is canonical and both failures lie on $\gamma_q$, the middle part uses no edge of $\pi$ outside $\gamma_q$. Hence the middle part decomposes into edges of $\gamma_q$ and maximal subpaths of $H$. Every edge of $\gamma_q$ on $\rho$ is different from $e$ and $e'$, so it is an edge of Type 1 of $K_q \setminus\{e,e'\}$. Every maximal subpath of $H$ starts at $v_i$ or at the head of an edge of $\gamma_q$ and ends at $v'_{i+1}$ or at the tail of an edge of $\gamma_q$; hence it connects two vertices $v_a,v_b \in V(\gamma_q)$, and its length is at least $\operatorname{dist}_{H}(v_a,v_b)$, the weight of the edge $(v_a,v_b)$ of Type 4. Replacing the prefix, the suffix, and every piece of the middle part by the corresponding kernel edge yields an $s'$–$t'$ walk of $K_q \setminus\{e,e'\}$ of length at most $|\rho|$, which proves the converse inequality.

By the above lemma, the algorithm of Lemma 5 answers all pairs of the block in $\widetilde{O}(L^3)$ time, and all $O(n/L)$ blocks in $\widetilde{O}(nL^2)$ time.

To construct the kernels, their edge weights have to be computed in a preprocessing step. The weights of Types 2, 3, and 5 are obtained by one forward and one reverse BFS in $G \setminus E(\gamma_q)$ per block, in $O(mn/L)$ time in total. The delicate part is the weights of Type 4, that is, the detour distances $\operatorname{dist}_{H}(v_a,v_b)$ for $v_a,v_b \in V(\gamma_q)$. A canonical replacement path for dual failures may also contain a backward detour, from $v_a$ to $v_b$ with $b<a$. Backward detours are not intercepted by $R$: the argument of Lemma 8 relies on the fact that a path climbing from layer $a$ to layer $b>a$ visits every layer in between, whereas a path descending from layer $a$ to layer $b<a$ may skip all separator layers in between. This is why we restrict the kernel to pairs inside one block: a detour between two vertices of the same block either stays within the layers of the block or leaves them and must climb back in through a separator layer, so the decomposition of Lemma 8 survives regardless of the order of $a$ and $b$.

Proof. The proof of Lemma 8 applies verbatim: it uses the order of $a$ and $b$ only to guarantee $\operatorname{dist}_{G}(s,v_b) \ge h_{q-1}$, which now holds by assumption. □

The distances $\operatorname{dist}_{H}(v_a,r)$ and $\operatorname{dist}_{H}(r,v_b)$ for all pivots $r$ are obtained by a forward and a reverse BFS in $H$ from each of the $|R| \le n/L$ pivots, in $O(mn/L)$ time, and the distances $\operatorname{dist}_{H_q}(v_a,v_b)$ by a BFS in $H_q$ from each of the at most $L+1$ vertices of $\gamma_q$; since every vertex and every edge of $H$ lies in at most two of the graphs $H_q$, these BFSs cost $O(mL)$ time in total. Evaluating the minimum of Lemma 14 for the at most $L^2$ pairs of a block takes $O(L^2 \cdot n/L)=O(nL)$ time, hence $O(n^2)$ time over all $O(n/L)$ blocks. Together with the $\widetilde{O}(nL^2)$ time for running the algorithm of Lemma 5 on every kernel, all edge pairs in the same block are handled deterministically in $\widetilde{O}(mL+mn/L+n^2+nL^2)=\widetilde{O}(mn^{3/4}+n^{5/2})$ time, recalling that $L=\lceil n^{3/4}\rceil$. The whole procedure is summarized in Algorithm 5.

Algorithm 5: Edge pairs in the same block

1. $\operatorname{dist}_{H}(r,*) \leftarrow\operatorname{BFS}(H,r)$ for each $r \in R$

2. $\operatorname{dist}_{H}(*,r) \leftarrow\operatorname{BFS}(H^{\mathrm{rev}},r)$ for each $r \in R$

3. foreach block $q$ do

4. $\operatorname{dist}_{G\setminus E(\gamma_q)}(s,*) \leftarrow\operatorname{BFS}(G\setminus E(\gamma_q),s)$

5. $\operatorname{dist}_{G\setminus E(\gamma_q)}(*,t) \leftarrow\operatorname{BFS}((G\setminus E(\gamma_q))^{\mathrm{rev}},t)$

6. $\operatorname{dist}_{H_q}(v,*) \leftarrow\operatorname{BFS}(H_q,v)$ for each $v \in V(\gamma_q)$

7. foreach $v_a,v_b \in V(\gamma_q)$ do

8. $\operatorname{dist}_{H}(v_a,v_b) \leftarrow\min\left\{\min_{r\in R}\{\operatorname{dist}_{H}(v_a,r)+\operatorname{dist}_{H}(r,v_b)\},\operatorname{dist}_{H_q}(v_a,v_b)\right\}$

9. Construct the weighted kernel $K_q$ by the procedure described in Kernel construction

10. Run the algorithm of Lemma 5 for $K_q$ and $s',t'$.

Edge Pairs in Different Blocks

Fix two distinct blocks $\gamma_p=\pi[v_a,v_b]$ and $\gamma_q=\pi[v_c,v_d]$, where $p+1\le q$ and hence $b\le c$. Let $e=(v_i,v_{i+1})\in E(\gamma_p)$ and $e'=(v_j,v_{j+1})\in E(\gamma_q)$, so that $a\le i<b\le c\le j<d$.

Let $\rho$ be a canonical shortest $s$–$t$ path in $G\setminus\{e,e'\}$. Such a path always exists. We distinguish four cases according to how $\rho$ traverses the portions of $\pi$ around the two failed edges. See Figure 4 for an illustration.

Case 1: $\rho$ does not use any edge of $\pi[v_{i+1},v_b]$.

Case 2: $\rho$ does not use any edge of $\pi[v_c,v_j]$.

Case 3: Neither Case 1 nor Case 2 occurs. Let $x$ be the minimum index such that $v_x \in V(\pi[v_{i+1},v_b]) \cap V(\rho)$, and let $y$ be the maximum index such that $v_y \in V(\pi[v_c,v_j]) \cap V(\rho)$. Note that such vertices $v_x$ and $v_y$ necessarily exist, since neither Case 1 nor Case 2 occurs. Suppose that $v_x$ appears at or before $v_y$ on $\rho$. Since $x \le b \le c \le y$, we have $v_x = v_y$ only if $b = c$ and $x = y = b$, which can happen when $q = p + 1$.

Case 4: Neither Case 1 nor Case 2 occurs, and, with $v_x$ and $v_y$ defined as in Case 3, $v_y$ appears strictly before $v_x$ on $\rho$.

For every pair of edges $(e,e')$ in different blocks, let $D_L(e,e')$, $D_R(e,e')$, $D_F(e,e')$, and $D_B(e,e')$ denote the minimum lengths of $s$–$t$ paths in $G \setminus\{e,e'\}$ satisfying the conditions of Cases 1, 2, 3, and 4, respectively. Then,

We next describe how to compute these candidates efficiently. Roughly speaking, we show that all of them can be obtained using only $O(n/L)$ SSRP computations.

Case 1: $\rho$ contains no edge of $\pi[v_{i+1},v_b]$. Let $v_z$ be the last vertex of $\rho$ in $\{v_0,\ldots,v_i\}$. Since $\pi[s,v_z]$ contains no failed edge, the canonicality of $\rho$ implies that $\rho[s,v_z]=\pi[s,v_z]$, and hence $|\rho[s,v_z]|=z$. Moreover, $\rho[v_z,t]$ contains no edge of $\gamma_p$. Indeed, by the choice of $v_z$, it cannot use an edge of $\pi[v_a,v_i]$, the edge $e$ is failed, and by the assumption of this case it uses no edge of $\pi[v_{i+1},v_b]$. Therefore, we have $|\rho|=z+\operatorname{dist}_{G\setminus(E(\gamma_p)\cup\{e'\})}(v_z,t)$.

Accordingly, define

Every term in the minimum corresponds to an $s$–$t$ walk avoiding both $e$ and $e'$, while the choice of $v_z$ above attains $|\rho|$. Hence, $|\rho|=D_L(e,e')$ in this case.

Computing $D_L$. For each block $\gamma_p$, let $G_p:=G\setminus E(\gamma_p)$ and run SSRP from $t$ in $G_p^{\mathrm{rev}}$. This gives, for every failed edge $e'$ and every vertex $v_z$, the distance $\operatorname{dist}_{G_p\setminus e'}(v_z,t)$. For each fixed $e'$, we then scan the vertices $v_0, v_1, \ldots$ in their order on $\pi$ and maintain the prefix minima $P_{e'}(i) := \min_{0 \le z \le i} \{z + \operatorname{dist}_{G_{P}\setminus e'}(v_z,t)\}$. Then, for every $e = (v_i,v_{i+1}) \in E(\gamma_p)$, we simply have $D_L(e,e') = P_{e'}(i)$.

Running time. There are $O(n/L)$ blocks. By Lemma 4, one call to SSRP takes $\widetilde{O}(m\sqrt{n} + n^2)$ time. Hence, the total time for the SSRP calls over all blocks is $\widetilde{O}\left(\frac{n}{L}(m\sqrt{n} + n^2)\right) = \widetilde{O}\left((mn^{3/2} + n^3)/L\right)$. Recall that there are only $O(n)$ possible choices for the second failed edge $e'$. The prefix-minimum scans require at most $O(n^2)$ additional time per block, and hence $O(n^3/L)$ time over all blocks. Consequently, all values $D_L(e,e')$ for edge pairs $(e,e')$ lying in different blocks can be computed in $\widetilde{O}\left((mn^{3/2} + n^3)/L\right)$ time.

Case 2: $\rho$ contains no edge of $\pi[v_c,v_j]$. This case is symmetric to Case 1. Let $v_z$ be the first vertex of $\rho$ in $\{v_{j+1},\ldots,v_k\}$. By canonicality, $\rho[v_z,t] = \pi[v_z,t]$, and hence $|\rho[v_z,t]| = k-z$. Moreover, $\rho[s,v_z]$ contains no edge of $\gamma_q$. Therefore, we define

Every term in the minimum corresponds to an $s$–$t$ walk avoiding both $e$ and $e'$, while the choice of $v_z$ above attains $|\rho|$. Hence, we have $|\rho| = D_R(e,e')$ in Case 2. To compute these values, for each block $\gamma_q$, we run SSRP from $s$ in $G\setminus E(\gamma_q)$. For each fixed failed edge $e$, a suffix-minimum scan along $\pi$ then gives $D_R(e,e')$ for every $e'=(v_j,v_{j+1})\in E(\gamma_q)$. As in Case 1, all values $D_R(e,e')$ can be computed in $\widetilde{O}((mn^{3/2}+n^3)/L)$ time.

Case 3: $v_x$ appears at or before $v_y$ on $\rho$. Since neither Case 1 nor Case 2 occurs, the vertices $v_x$ and $v_y$ are well defined. Recall that $x$ is the minimum index such that $v_x \in V(\pi[v_{i+1},v_b])\cap V(\rho)$, and $y$ is the maximum index such that $v_y \in V(\pi[v_c,v_j])\cap V(\rho)$. Thus, $i < x \le b \le c \le y \le j$. Hence, $\pi[v_x,v_y]$ contains neither $e$ nor $e'$. Since $v_x$ appears at or before $v_y$ on both $\pi$ and $\rho$, the canonicality of $\rho$ implies that $\rho[v_x,v_y] = \pi[v_x,v_y]$.

Moreover, $\rho[s,v_b]$ uses no edge of $\pi[v_b,t]$, and $\rho[v_c,t]$ uses no edge of $\pi[s,v_c]$. Therefore, $\rho[s,v_b]$ uses only edges of $G\setminus E(\pi[v_b,t]) = H+\pi[s,v_b]$ and avoids $e$. Recall that $H := G\setminus E(\pi)$. Similarly, $\rho[v_c,t]$ uses only edges of $G\setminus E(\pi[s,v_c]) = H+\pi[v_c,t]$ and avoids $e'$.

Accordingly, define

In Case 3, we have $|\rho| = D_F(e,e')$. The key observation is that $e'$ is absent from $H+\pi[s,v_b]$, while $e$ is absent from $H+\pi[v_c,t]$. Hence, each of the two distance terms in $D_F(e,e')$ involves only one failed edge.

Computing $D_F$ and its running time. For every block $\gamma_p = \pi[v_a,v_b]$, run SSRP from $s$ in $H+\pi[s,v_b]$. This gives $\operatorname{dist}_{(H+\pi[s,v_b])\setminus e}(s,v_b)$ for every $e \in E(\gamma_p)$. Symmetrically, for every block $\gamma_q = \pi[v_c,v_d]$, run SSRP from $t$ in $(H+\pi[v_c,t])^{\mathrm{rev}}$. This gives $\operatorname{dist}_{(H+\pi[v_c,t])\setminus e'}(v_c,t)$ for every $e' \in E(\gamma_q)$. Once these values are available, $D_F(e,e')$ can be obtained in constant time for every pair $(e,e')$.

There are $O(n/L)$ blocks, and each SSRP call takes $\widetilde{O}(m\sqrt{n}+n^2)$ time by Lemma 4. Hence, all values $D_F(e,e')$ can be computed in $\widetilde{O}((mn^{3/2}+n^3)/L)$ time, together with $O(n^2)$ additional time to compute $D_F(e,e')$ for all edge pairs $(e,e')$.

Case 4: $v_y$ appears strictly before $v_x$ on $\rho$. Let $S_p := \{u \in V \mid\operatorname{dist}_G(s,u) = b\}$ and $T_q := \{w \in V \mid\operatorname{dist}_G(s,w) = c\}$. Let $u$ be the first vertex of $\rho$ in $S_p$, and let $w$ be the last vertex of $\rho$ in $T_q$. See Figure 5 for an illustration.

By the choice of $u$, the prefix $\rho[s,u]$ contains no edge of $\pi[v_b,t]$. This is because every vertex of $\rho[s,u)$ has distance from $s$ strictly less than $b$. Similarly, by the choice of $w$, the suffix $\rho[w,t]$ contains no edge of $\pi[s,v_c]$. Define

We next consider the middle portion $\rho[u,w]$. Let $v_f$ be the first vertex of $\rho[u,w]$ in $\pi[v_{i+1},v_b]$, and let $v_g$ be the last vertex of $\rho[u,w]$ in $\pi[v_c,v_j]$. Such vertices exist since $\rho[u,w]$ contains both $v_x$ and $v_y$.

To analyze the two subpaths $\rho[u,v_f]$ and $\rho[v_g,w]$, we first establish the following claim.

Proof. Suppose first that $\rho[u,w]$ visits some $v_r$ with $r \le i$. Since $\pi[s,v_r]$ contains no failed edge, canonicity implies $\rho[s,v_r] = \pi[s,v_r]$. However, $\rho[s,v_r]$ contains $u$, while $\operatorname{dist}_G(s,u) = b > r$, a contradiction.

Similarly, if $\rho[u,w]$ visits some $v_r$ with $r \ge j+1$, then $\pi[v_r,t]$ contains no failed edge, and canonicity implies $\rho[v_r,t] = \pi[v_r,t]$. Since $\rho[v_r,t]$ contains $w$, this would imply $w \in V(\pi[v_r,t])$. However, every vertex on $\pi[v_r,t]$ has distance at least $r$ from $s$, whereas $\operatorname{dist}_G(s,w) = c < r$, a contradiction. $\square$

By Claim 15 and the choice of $v_f$, the subpath $\rho[u,v_f]$ contains no edge of $\pi[s,v_b]$. Indeed, otherwise it would use some edge $(v_r,v_{r+1})$ with $i+1 \le r < b$, and hence visit a vertex of $\pi[v_{i+1},v_b]$ before $v_f$, contradicting the choice of $v_f$. Similarly, by Claim 15 and the choice of $v_g$, the subpath $\rho[v_g,w]$ contains no edge of $\pi[v_c,t]$. Hence, $\rho[u,v_f] \subseteq H+\pi[v_b,t]$ and $\rho[v_g,w] \subseteq H+\pi[s,v_c]$.

Now, define

There are two cases depending on the order of $v_f$ and $v_g$ on $\rho$.

Case 4.1: $v_g$ appears at or before $v_f$ on $\rho$. In this case, $v_f$ lies on $\rho[v_g,w]$, and hence the middle portion $\rho[u,w]$ can be split at $v_f$ into $\rho[u,v_f]$ and $\rho[v_f,w]$. In this case, we decompose $\rho[u,w]$ as $\rho[u,v_f] \circ\rho[v_f,w]$. Accordingly, define

Case 4.2: $v_f$ appears before $v_g$ on $\rho$. Since $i+1 \le f \le b \le c \le g \le j$ the subpath $\pi[v_f,v_g]$ contains neither failed edge. By canonicality, $\rho[v_f,v_g] = \pi[v_f,v_g]$. Thus, the two middle portions $\rho[u,v_f]$ and $\rho[v_g,w]$ are connected by the subpath $\pi[v_f,v_g]$. In this case, we decompose $\rho[u,w]$ as $\rho[u,v_f] \circ\pi[v_f,v_g] \circ\rho[v_g,w]$. Accordingly, define

Combining Cases 4.1 and 4.2. Accordingly, define

Every term in the minimum corresponds to an $s$–$t$ walk in $G\setminus\{e,e'\}$. Conversely, the canonical path $\rho$ determines suitable vertices $u,w,f,g$, and hence one of the above terms has length $|\rho|$. Therefore, in Case 4, we have $|\rho|=D_{\mathrm{B}}(e,e')$.

Computing $A$, $B$, $U$, and $V$. All required values $A$, $B$, $U$, and $V$ can all be computed using SSRP. For each block $\gamma_p=\pi[v_a,v_b]$, we run SSRP from $s$ in $H+\pi[s,v_b]$ to compute all values $A_e(u)$. Similarly, for each block $\gamma_q=\pi[v_c,v_d]$, we run SSRP from $t$ in $(H+\pi[v_c,t])^{\mathrm{rev}}$ to compute all values $B_{e'}(w)$.

For each vertex $u\in S_p$, we run SSRP from $u$ in $H+\pi[v_b,t]$ to compute all values $U_e^u(z)$. Similarly, for each vertex $w\in T_q$, we run SSRP from $w$ in $(H+\pi[s,v_c])^{\mathrm{rev}}$ to compute all values $V_e^w(z)$.

By Lemma 4, one call to SSRP takes $\widetilde{O}(m\sqrt{n}+n^2)$ time. There are $O(n/L)$ blocks, and by the definition of the modulo-layer hitting set, we have $\sum_p |S_p|=O(n/L)$ and $\sum_q |T_q|=O(n/L)$. Hence, the total number of SSRP calls is $O(n/L)$. Therefore, all required values $A$, $B$, $U$, and $V$ can be computed in $\widetilde{O}((mn^{3/2}+n^3)/L)$ time.

Computing $D_{\mathrm{B}}$. Fix $u\in S_p$ and $w\in T_q$. There are $O(L)$ possible choices for $e\in E(\gamma_p)$ and $O(L)$ possible choices for $e'\in E(\gamma_q)$. For each fixed pair $(e,e')$, the value $M_{e,e'}^{u,w}$ can be computed by scanning the $O(L)$ possible indices $f$. Similarly, each of $\min_{i+1\le f\le b}\{U_{e'}^u(f)-f\}$ and $\min_{c\le g\le j}\{g+V_e^w(g)\}$ can be computed in $O(L)$ time. Hence, $C_{e,e'}^{u,w}$ can also be computed in $O(L)$ time. Therefore, all required values $M_{e,e'}^{u,w}$ and $C_{e,e'}^{u,w}$ for the fixed pair $(u,w)$ can be computed in $O(L^3)$ time.

The total number of pairs $(u,w)$ over all pairs of blocks is at most

Consequently, the total time for computing all values $M_{e,e'}^{u,w}$ and $C_{e,e'}^{u,w}$ is $O\left(\frac{n^2}{L^2}\cdot L^3\right)=O(n^2L)$.

Finally, all values $D_{\mathrm{B}}(e,e')$ can be computed in $\widetilde{O}\left(\frac{mn^{3/2}+n^3}{L}+n^2L\right)$ time.

Total running time. From Cases 1–4, all values $D_{\mathrm{L}}(e,e')$, $D_{\mathrm{R}}(e,e')$, $D_{\mathrm{F}}(e,e')$, $D_{\mathrm{B}}(e,e')$ can be computed in $\widetilde{O}\left(\frac{mn^{3/2}+n^3}{L}+n^2L\right)$ time. Therefore, all values $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ for pairs $(e,e')$ lying in different blocks can be computed in $\widetilde{O}\left((mn^{3/2}+n^3)/L+n^2L\right)=\widetilde{O}(n^{3-1/4})$ total time, recalling that $L=\lceil n^{3/4}\rceil$.

Concluding Remarks

In this work, we introduced the modulo-layer hitting set technique and showed that this simple idea is useful for both single-failure and dual-failure replacement paths in unweighted directed graphs. For RP, in particular, it leads to a remarkably simple deterministic algorithm that is suitable for textbook presentation and practical implementation. We believe that this technique may be useful more broadly in other shortest-path problems.

For 2-FRP, the modulo-layer hitting-set technique allows us to solve the problem using MSRP and SSRP as subroutines. Our algorithm can be viewed as a weak form of a reduction from directed 2-FRP to MSRP and SSRP. Roughly speaking, our algorithm reduces directed 2-FRP to a constant number of MSRP instances with $O(\sqrt{n})$ sources and $O(n^{1/4})$ SSRP instances.

Finally, the only randomization in our 2-FRP algorithm comes from the MSRP algorithm by Harada and Izumi [22]. Thus, a deterministic MSRP algorithm with the same running time as that of Harada and Izumi would immediately yield a deterministic $\widetilde{O}(n^{3-1/4})$-time algorithm for 2-FRP.

Acknowledgements. Kaito Harada was supported by JST BOOST, Japan Grant Number JP-MJBS2402.

AI Disclosure. The main ideas behind our RP and 2-FRP algorithms were developed largely with the assistance of GPT-6 Astra (OpenAI). The authors’ contributions include simplifying several of the resulting algorithms, unifying the underlying techniques under the modulo-layer hitting set, developing the idea of using MSRP to improve the running time for 2-FRP when one failed edge lies on $\pi$, and the entire design and analysis of the algorithm for this case (Lemma 9). We also used GPT-6 Astra (OpenAI) and Claude Fable 5.1 (Anthropic) to assist with language editing and improving the presentation of parts of the manuscript. All proofs and the text of this paper were written and verified by the authors, who take full responsibility for its content.

One Failure on $\pi$

This appendix completes the proof of Lemma 9. We describe the overall algorithm that computes all values $\operatorname{dist}_{G\setminus\{e,e'\}}(s,t)$ with $e \in E(\pi)$ and $e' \notin E(\pi)$ from the distances of Algorithm 4, and analyze its running time.

Pairs to be computed. Recall from § 4 that $\rho_{e_i}$ denotes a fixed replacement path for $e_i=(v_i,v_{i+1})\in E(\pi)$, and that only the second failures $e'\in E(\rho_{e_i})\setminus E(\pi)$ need to be considered. Let

where $E(\rho_{e_i}):=\varnothing$ if $e_i$ has no replacement path. Then $|\mathcal{K}|<n^2$, and every pair of $\mathcal{K}$ has $e'\in E(H)$.

Overall algorithm. Consider a pair $(i,e')\in\mathcal{K}$. Lemmas 10 and 11 are Lemmas 7 and 8 with $H$ replaced by $H\setminus e'$, and the derivation of § 3 applies verbatim to them. Hence

where $C_i(e')$ and $S_i(e')$ are the candidates $C_i$ and $S_i$ of § 3 with $\operatorname{dist}_H$ and $\operatorname{dist}_{H_{q(i)}}$ replaced by $\operatorname{dist}_{H\setminus e'}$ and $\operatorname{dist}_{H_{q(i)}\setminus e'}$. Accordingly, let $A^{e'}(r)$, $B^{e'}(r)$, and $W^{e'}_{q,a}$ denote the tables that the scans of Algorithm 3 build with these distances; then

In particular, running lines 2–19 of Algorithm 3 with the distances of $H\setminus e'$ computes $\min\{C_i(e'),S_i(e')\}$ for all $i$. Doing so for every $e'\in E(H)$ takes $O(n^2/L+nL)$ time per edge, hence $O(mn^2/L+mnL)$ time in total, which is too slow. The algorithm below avoids this by reusing the scans of Algorithm 3 across different $e'$, and by evaluating the candidates only for the pairs of $\mathcal{K}$.

Reusing scans. Every scan of Algorithm 3 reads only the distances from a single source $u$ of Algorithm 4: from $r$ in $H^{\mathrm{rev}}$ for $A^{e'}(r)$, from $r$ in $H$ for $B^{e'}(r)$, and from $v_a$ in $H_q$ for $W^{e'}_{q,a}$. Let $T_u$ be the shortest-path tree of $u$ fixed by the MSRP call (edges of $H^{\mathrm{rev}}$ identified with those of $H$), and write $T_r^{\mathrm{in}}$, $T_r^{\mathrm{out}}$, and $T_{q,a}$ for the three kinds of sources. If $e'\notin E(T_u)$, removing $e'$ does not change the distances from $u$ (§ 2.3), so the table of $u$ for $e'$ equals the table $A(r)$, $B(r)$, or $W_{q,a}$ that Algorithm 3 builds for $H$, which we call the default table of $u$. Hence, for each $e'\in E(H)$, the algorithm rebuilds only the tables of the sources $u$ with $e'\in E(T_u)$, and lets every other table refer to the default table without copying it. Since $T_u$ has at most $n-1$ edges, each source rebuilds its table for at most $n-1$ edges $e'$. Over all $e'$, the $|R|\le n/L$ pivots thus rebuild $O(n)$ tables of $k<n$ entries each, in $O(n^3/L)$ time, and the at most $L+1$ path vertices of a block $V_q$ rebuild at most $|V_q|-1$ tables of at most $L$ entries each, in $O(nL^2)$ time since $\sum_q|V_q|\le2n$. Whether $e'=(x,y)$ lies in $E(T_u)$ is decided in $O(1)$ time by checking whether $x$ is the parent of $y$ in $T_u$ (or $y$ of $x$ for $T_r^{\mathrm{in}}$), and $e'$ can lie in $T_{q,a}$ only for the at most two blocks $V_q$ that contain both endpoints of $e'$. The decisions thus take $O(m(n/L+L))$ time in total, which is dominated by the time of Algorithm 4.

Running time. Line 1 of Algorithm 6 takes $O(m)$ time for Algorithm 1 and, as computed in § 4, $\widetilde{O}(mn/\sqrt{L}+n^3/L+mn\sqrt{nL}+n^2L)$ time for Algorithm 4, whose output we store so that every distance is accessed in $O(1)$ time. Line 2 takes $O(n^2/L+nL)$ time by § 3, and line 3 takes $O(n^2)$ time, since $\rho_{e_i}$ is read off in $O(n)$ time from a minimizer of $\min\{C_i,S_i\}$ recorded in line 2 and the shortest-path trees of the MSRP calls, as the concatenation of $\pi[s,v_a]$, a shortest $v_a$–$v_b$ path of $H$ through a pivot or inside $H_{q(i)}$, and $\pi[v_b,t]$. Over all $e' \in E(H)$, lines 5–12 take $O(m(n/L+L)+n^3/L+nL^2)$ time by the analysis above, and lines 13–17 take $O(n/L+L)$ time per pair of $\mathcal{K}$, hence $O(n^3/L+n^2L)$ time. Since $nL^2 \le n^2L$, $mn/L \le mn/\sqrt{L}$, and $mL \le m\sqrt{nL}$, the total running time is

For $L=\lceil\sqrt{n}\rceil$, this is $\widetilde{O}(mn^{3/4}+n^{5/2})$, which proves Lemma 9.