pipette
ESEspañol

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

Kaito Harada, Tatsuya Terao

Preprint

In the authors' words

We study the replacement paths problem in unweighted directed graphs with vertices and 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 modulo-layer hitting sets. For the single-failure setting, we obtain a simple deterministic combinatorial algorithm running in time, which is nearly optimal under the combinatorial Boolean Matrix Multiplication (BMM) conjecture. In addition to removing the logarithmic overhead of the deterministic -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 time. This improves upon the previous -time combinatorial algorithm of Chechik and Zhang~[ICALP'24].

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 25 pages