# Simpler and Improved Replacement Path Coverings

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

- Archive id: arxiv:2604.27966
- Published: 2026-04-30
- arXiv: https://arxiv.org/abs/2604.27966
- Source URL: https://arxiv.org/abs/2604.27966
- PDF: https://arxiv.org/pdf/2604.27966
- Provenance: arxiv

## Abstract

An important tool in the design of fault-tolerant graph data structures are $(L,f)$-replacement path coverings (RPCs). An RPC is a family $\\mathcal{G}$ of subgraphs of a given graph $G$ 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 covering value of the RPC is the total number $\|\\mathcal{G}\|$ of subgraphs. The query time is the time needed to compute the subfamily $\\mathcal{G}\_F$ given the set $F$. Weimann and Yuster \[TALG'13\] devised a randomized RPC with covering value $\\widetilde{O}(fL^f)$ and query time $\\widetilde{O}(f^2 L^f)$. This was derandomized by Karthik and Parter \[TALG'24\], who also reduced the query time to $\\widetilde{O}(f^2 L)$. Their approach uses some heavy algebraic machinery involving error-correcting codes and an increased covering value of $O((cfL \\log n)^{f+1})$ for some constant $c \> 1$. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to $\\widetilde{O}(fL^{f+o(1)})$ and decreases the query time to $\\widetilde{O}(f^{5/2}L^{o(1)})$, assuming $f = o(\\log L)$. We also investigate the optimal covering value of any $(L,f)$-replacement path covering (deterministic or randomized) for different parameter ranges. We provide a new randomized construction as well as improving a known lower bound, also by Karthik and Parter. For example, for $f = o(\\log L)$, we give an RPC with $\\widetilde{O}( (L/f)^f L^{o(1)})$ subgraphs and show that this is tight up to the $L^{o(1)}$ term.

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