English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper considers a natural fault-tolerant shortest paths problem: forsome constant integer $f$, given a directed weighted graph with no negativecycles and two fixed vertices $s$ and $t$, compute (either explicitly orimplicitly) for every tuple of $f$ edges, the distance from $s$ to $t$ if theseedges 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$-vertexdirected graphs with arbitrary edge weights and no negative cycles. As $2$FRPis a generalization of the well-studied Replacement Paths problem (RP) thatasks for the distances between $s$ and $t$ for any single edge failure, $2$FRPis at least as hard as RP. Since RP in graphs with arbitrary weights isequivalent 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 ashard as APSP, and thus a substantially subcubic time algorithm in the number ofvertices 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 firstimprovement over the straightforward $O(n^{f+2})$ time algorithm.  Then we focus on the restriction of $2$FRP to graphs with small integerweights bounded by $M$ in absolute values. Using fast rectangular matrixmultiplication, 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 alsopresent a data structure variant of the algorithm that can trade offpre-processing and query time. In addition to the algebraic algorithms, we alsogive an $n^{8/3-o(1)}$ conditional lower bound for combinatorial $2$FRPalgorithms in directed unweighted graphs.

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures