# Near-Optimal Replacement Path Coverings

Preprint · Davide Bilò, Keerti Choudhary, Sarel Cohen, Martin Schirneck

- Archive id: arxiv:2608.07124
- Published: 2026-08-07
- arXiv: https://arxiv.org/abs/2608.07124
- Source URL: https://arxiv.org/abs/2608.07124
- PDF: https://arxiv.org/pdf/2608.07124
- Provenance: arxiv

## Abstract

Let $L$ and $f$ be positive integers. An $(L,f)$-replacement path covering (RPC) for a graph $G$ is a family $\\mathcal{G}$ of subgraphs such that, for every set $F$ of at most $f$ edges, there is a subfamily $\\mathcal{G}\_F \\subseteq \\mathcal{G}$ with the following properties. (1) No subgraph in $\\mathcal{G}\_F$ contains an edge of $F$. (2) For each pair of vertices $s,t$ that have a shortest path in $G{-}F$ with at most $L$ edges, one such path also exists in some subgraph in $\\mathcal{G}\_F$. The total number $\|\\mathcal{G}\|$ of subgraphs is called the covering value. RPCs are an important tools in the design of fault-tolerant data structures. Weimann and Yuster \[TALG 2013\] presented an RPC with covering value $\\widetilde{O}(f L^f)$. Karthik and Parter \[TALG 2024\] showed that $Ω( (L/f)^f )$ subgraphs are necessary. Recently, Bilò, Chechik, Choudhary, Cohen, and Schirneck \[ICALP 2026\] devised a new approach for very small sensitivities $f = o(\\log L)$ with covering value $\\widetilde{O}(f e^f (L/f)^{f+o(1)})$. They also showed that any RPC in the complementary range $f = Ω(\\log L)$ must contain $Ω( (\\sqrt{f e^f}/L) \\cdot (L/f)^f)$ subgraphs. This left open the question of what is the true covering value. We give two surprisingly simple constructions that improve both the upper and lower bound. This results in a near-tight covering value of $\\widetildeΘ(\\frac{(L+f)^{L+f}}{L^L f^f}) \\cdot \\mathsf{poly}(f)$ for the much wider range of $f = O(L)$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
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.