论文标题
在多个边缘失败下的替换路径的算法和下限
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
论文作者
论文摘要
本文考虑了自然容忍的最短路径问题：对于某些恒定整数$ f $，鉴于没有负循环的定向加权图和两个固定的顶点$ s $和$ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ f $。我们称此问题$ f $ -fault替换路径（$ f $ frp）。 我们首先提出一个$ \ tilde {o}（n^3）$ time算法，价格为$ 2 $ frp，$ n $ vertex有向图的图形，具有任意边缘权重，没有负面周期。由于$ 2 $ frp是对良好的替换路径问题（RP）的概括，该问题要求任何单个边缘故障的$ s $和$ t $之间的距离，因此$ 2 $ frp至少与RP一样困难。由于在具有任意权重的图中的RP在细粒度上与最短路径（APSP）[Vassilevska Williams和Williams focs'10，J.〜ACM'18]相当，因此$ 2 $ frp至少与APSP一样困难，因此在$ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ f.因此，我们在$ \ tilde {o}（n^3）$ time中的算法几乎是最佳的。我们的算法意味着$ \ tilde {o}（n^{f+1}）$ f $ f $ frp问题的$ time算法，从而对直接的$ o（n^{f+2}）$ time Algorithm进行了第一个改进。 然后，我们专注于$ 2 $ frp对图形的限制，其整数重量小于$ m $的绝对值。使用快速矩形矩阵乘法，我们获得了一个随机算法，该算法在$ \ tilde {o}（m^{2/3} n^{2.9153}）$ time中运行。这意味着对我们的$ \ tilde {o}（n^{f+1}）$ time time time tunsive算法算法的改进。我们还提出了算法的数据结构变体，可以权衡预处理和查询时间。除了代数算法外，我们还提供了$ n^{8/3-o（1）} $组合中有条件的下限$ 2 $ 2 $ frp算法，以定向的未加权图。
This paper considers a natural fault-tolerant shortest paths problem: for some constant integer $f$, given a directed weighted graph with no negative cycles and two fixed vertices $s$ and $t$, compute (either explicitly or implicitly) for every tuple of $f$ edges, the distance from $s$ to $t$ if these edges fail. We call this problem $f$-Fault Replacement Paths ($f$FRP). We first present an $\tilde{O}(n^3)$ time algorithm for $2$FRP in $n$-vertex directed graphs with arbitrary edge weights and no negative cycles. As $2$FRP is a generalization of the well-studied Replacement Paths problem (RP) that asks for the distances between $s$ and $t$ for any single edge failure, $2$FRP is at least as hard as RP. Since RP in graphs with arbitrary weights is equivalent in a fine-grained sense to All-Pairs Shortest Paths (APSP) [Vassilevska Williams and Williams FOCS'10, J.~ACM'18], $2$FRP is at least as hard as APSP, and thus a substantially subcubic time algorithm in the number of vertices for $2$FRP would be a breakthrough. Therefore, our algorithm in $\tilde{O}(n^3)$ time is conditionally nearly optimal. Our algorithm implies an $\tilde{O}(n^{f+1})$ time algorithm for the $f$FRP problem, giving the first improvement over the straightforward $O(n^{f+2})$ time algorithm. Then we focus on the restriction of $2$FRP to graphs with small integer weights bounded by $M$ in absolute values. Using fast rectangular matrix multiplication, we obtain a randomized algorithm that runs in $\tilde{O}(M^{2/3}n^{2.9153})$ time. This implies an improvement over our $\tilde{O}(n^{f+1})$ time arbitrary weight algorithm for all $f>1$. We also present a data structure variant of the algorithm that can trade off pre-processing and query time. In addition to the algebraic algorithms, we also give an $n^{8/3-o(1)}$ conditional lower bound for combinatorial $2$FRP algorithms in directed unweighted graphs.
