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

Preprint · Kaito Harada, Tatsuya Terao

- Archive id: arxiv:2610.24817
- Published: 2026-10-17
- arXiv: https://arxiv.org/abs/2610.24817
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.24817
- PDF: https://arxiv.org/pdf/2610.24817
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.