Undirected 3-Fault Replacement Path in Nearly Cubic Time

We consider an undirected weighted graph $G=(V,E)$ and $n=|V|,m=|E|$. For any two vertices $u,v\in V$, we use ${\pi }_G(u,v)$ to denote the shortest path from $u$ to $v$ in $G$. If the graph is clear in the context, then we use $uv$ to be short for ${\pi }_G(u,v)$. For a path $P$, we use $|P|,\Vert P\Vert$ to denote the length of $P$ and the number of edges in $P$, respectively.

If the context is clear that a vertex $z$ is on the shortest path ${\pi }_G(u,v)$ from $u$ to $v$ in a graph $G$, we use $z\oplus i$ to represent the vertex that is $i$ vertices after $z$ in the direction from $u$ to $v$. Similarly, we define $z\ominus i$ to represent the vertex that is $i$ vertices before $z$. When vertices $u$ and $v$ and the shortest path $uv$ are clear in the context, for two vertices $x$ and $y$ on $uv$, we use the notation $x>y$ to say that $x$ is farther than $y$ from $u$, or $\Vert ux\Vert >\Vert uy\Vert$. Similarly means , $x\le y$ means $\Vert ux\Vert \le \Vert uy\Vert$, $x\ge y$ means $\Vert ux\Vert \ge \Vert uy\Vert$.

If $x,y\in uv$, ${\pi }_G(x,y)$ will be the subpath from $x$ to $y$ on $uv$, and if $x\le y$, we use the interval $[x,y]$ to denote the subpath ${\pi }_G(x,y)$ of $uv$ in graph $G$. Thus the interval between $i$-th vertex and $j$-th vertex after $u$ on $uv$ is denoted as $R=[u\oplus i,u\oplus j]$.

Let $P_1,P_2$ be two paths. If they share a same endpoint, we use $P_1\circ P_2$ to denote the concatenation of them. If they do not share any edge, we say $P_1$ avoids $P_2$. Sometimes for brevity, we use $\min \{P_1,P_2\}$ to denote the shorter path of $P_1,P_2$, which means if $|P_1|\le |P_2|$, $\min \{P_1,P_2\}=P_1$ and otherwise $\min \{P_1,P_2\}=P_2$.

In this paper, for a path $P$ in $G$, $G-P$ denotes the graph obtained by removing all edges of $P$ from $G$. (We do not need to remove vertices in this paper.)

As in many distance oracle papers, we also use the unique shortest path assumption, which means the shortest path between any two vertices in any subgraph of $G$ is unique. For the incremental DSO, we also make the unique shortest path assumption at any time. So for example, we can check whether an edge $e=(x,y)$ is on $st$ or not by checking whether $|sx\circ (x,y)\circ yt|=|st|$ or $|sy\circ (y,x)\circ xt|=|st|$. To assume unique shortest path, we can break the ties by adding small perturbations to the edge weights. (See [10].) One way to assume unique shortest path deterministically is to compare two paths of the same length by their number of edges, then by their vertices from the end node to start node.

We first consider the divergence and convergence points of two paths: (As before, although our graph is undirected, we may assume a path $P$ starts from a vertex $u$ and ends at $v$.)

• $\mathrm{■}$

  For two paths $P,Q$ both starting from $u$, we say they diverge at vertex $a\in P\cap Q$ if $Q$ first gets into an edge out of $P$ from $a$, that is, the subpaths of $P$ and $Q$ before $a$ coincide, and we denote this divergence point $a$ by $\mathrm{\Delta }(P,Q)$. If $P,Q$ are both shortest paths, their divergence point is unique.

• $\mathrm{■}$

  Symmetrically, for $P,Q$ both ends at $v$, we say they converges at vertex $b\in P\cap Q$ if $Q$ gets into an edge in $P$ from $b$, and the subpaths of $P$ and $Q$ coincide after $b$. The convergence point $b$ is denoted by $\nabla (P,Q)$.

• $\mathrm{■}$

  For two shortest paths $P,Q$ which do not share endpoints, if they intersect, the intersection part is also a shortest path, that is, they must first converge and then diverge.

The following theorem is well known for replacement paths.

From this theorem, we can see for any $f$-fault replacement path ${\pi }_{G-F}(u,v)$ where only one failed edge in $F$ is on the original shortest path $uv$, ${\pi }_{G-F}(u,v)$ only diverges and converges once on $uv$. And if two failed edges $d_1,d_2$ in $F$ are on $uv$, they will cut $uv$ into three intervals $D_1,D_2,D_3$. Because $D_1,D_2,D_3$ are all shortest paths in $G-F$, ${\pi }_{G-F}(u,v)$ may:

• $\mathrm{■}$

  diverge at $D_1$ and converge at $D_3$.

• $\mathrm{■}$

  diverge at $D_1$, converge at some point in $D_2$, diverge from $D_2$, then converge at $D_3$.

In undirected weighted graphs, a notable theorem on the structure of replacement paths says that a 1-fault replacement path ${\pi }_{G-f}(u,v)$ is a concatenation of a shortest path $ux$, an edge $e=(x,y)$, and a shortest path $yv$, for some vertices $x$ and $y.$ (Any part can degenerate to a point.) More generally,

From this theorem, we have:

The paper uses the 1-fault DSO given by Bernstein and Karger [4] to initialize the incremental DSO. While [4] gives a 1-fault DSO in directed weighted graphs, it also works for undirected weighted graphs by a simple reduction. Suppose $G$ is an undirected weighted graph, we introduce a directed graph $G^{\prime }$ by replacing each edge in $G$ by a pair of directed edges with the same weight. Suppose that in graph $G$ edge $(x,y)$ on the shortest path $st$ is removed ($x$ is closer to $s$), then we remove the directed edge $(x,y)$ on the shortest path from $s$ to $t$ in $G^{\prime }.$ We can see that the 1-fault replacement path ${\pi }_{G^{\prime }-(x,y)}(s,t)$ cannot go through edge $(y,x).$ This is because that no edge on ${\pi }_{G^{\prime }}(s,x)$ is removed, so ${\pi }_{G^{\prime }-(x,y)}(s,x)={\pi }_{G^{\prime }}(s,x)$ does not go through $(y,x).$ Therefore, ${\pi }_{G-(x,y)}(s,t)={\pi }_{G^{\prime }-(x,y)}(s,t).$

There is a result in [27] to view worst-case incremental structures as offline fully dynamic structures.

This theorem can be used to utilize our incremental DSO in Section 3.2 as an offline fully dynamic DSO, and here we also prove the reduction we need in a self-contained way:

All 1-fault replacement paths are easy to find in $\tilde{O}(mn)$ time since we can delete each edge on $st$ and then run Dijkstra’s algorithm [14] from $s$. Then for edges $d_1\in st$ and $d_2\in {\pi }_{G-d_1}(s,t)$, consider whether $d_2$ is on $st$ or not.

In 3FRP problem, consider the case that only $d_1$ is on $st$ but $d_2,d_3$ are not, the 2-failure DSO of $\tilde{O}(n^2)$ space and $\tilde{O}(1)$ query time [18] cannot be directly applied here since its construction time is too large. However, since the number of possible “second failures” $d_2$ is $O(n)$ by Lemma 9, a dynamic 1-failure DSO with $\tilde{O}(n^2)$ edge update time will help. We can delete every $d_2$, query for every $d_1$ and $d_3$ as the method in Section 3.1.1, then add $d_2$ back.

Thus below we first introduce ideas toward Theorem 2 to build an incremental DSO with construction time $\tilde{O}(n^3)$, worst-case update time $\tilde{O}(n^2)$ and query time $\tilde{O}(1)$. By the reduction in Theorem 11, we can construct an offline dynamic DSO with $\tilde{O}(n^2)$ update time. In the incremental DSO, when inserting an edge $e=(x,y)$, let $G^{\prime }$ be the new graph $G^{\prime }=G\cup e$.