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

Abstract

We study the replacement paths problem in unweighted directed graphs with $n$ vertices and $m$ edges under one or two edge failures. We give simpler and faster algorithms for both settings. Both algorithms are based on a new technique, which we call \emph{modulo-layer hitting sets}. For the single-failure setting, we obtain a simple deterministic combinatorial algorithm running in $O(m\sqrt{n})$ time, which is nearly optimal under the combinatorial Boolean Matrix Multiplication (BMM) conjecture. In addition to removing the logarithmic overhead of the deterministic $\tilde{O}(m\sqrt{n})$-time algorithm of Alon, Chechik, and Cohen~[ICALP'19], our algorithm admits a much simpler implementation and analysis. For the dual-failure setting, we obtain a randomized combinatorial algorithm running in $\tilde{O}(n^{3-1/4})$ time. This improves upon the previous $\tilde{O}(n^{3-1/18})$-time combinatorial algorithm of Chechik and Zhang~[ICALP'24].

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.