Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
share
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 (fFRP). We first present an Õ(n^3) time algorithm for 2FRP in n-vertex directed graphs with arbitrary edge weights and no negative cycles. As 2FRP 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, 2FRP 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], 2FRP is at least as hard as APSP, and thus a substantially subcubic time algorithm in the number of vertices for 2FRP would be a breakthrough. Therefore, our algorithm in Õ(n^3) time is conditionally nearly optimal. Our algorithm implies an Õ(n^f+1) time algorithm for the fFRP problem, giving the first improvement over the straightforward O(n^f+2) time algorithm. Then we focus on the restriction of 2FRP 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 Õ(M^2/3n^2.9153) time. This implies an improvement over our Õ(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 2FRP algorithms in directed unweighted graphs.
READ FULL TEXT