Simpler faster algorithms improve fault-tolerant routes in directed graphs
Simplified and Faster Algorithms for the Directed Single/Dual-Failure Replacement Paths via Modulo-Layer Hitting Sets
Data Structures and Algorithms
Summary
When a path in a network has a broken connection, the replacement paths problem is about quickly finding alternate routes. This paper presents new methods that simplify and speed up finding these alternate paths in directed graphs when one or two connections fail. The authors introduce a novel technique called modulo-layer hitting sets, offering faster algorithms without complex overhead. Their single-failure solution is nearly as fast as theoretically possible with simpler design, while their two-failure method improves previous speeds using a randomized approach.
What this means in practice
- •For network engineers: Improve algorithms for quickly rerouting traffic when one or two network links fail to maintain service reliability.
- •For transportation planners: Speed up calculation of alternate paths for traffic flow when road segments are closed due to accidents or maintenance.
Authors
Kaito Harada, Tatsuya Terao
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].