{"id":"arxiv:2604.27966","kind":"preprint","title":"Simpler and Improved Replacement Path Coverings","authors":["Davide Bilò","Shiri Chechik","Keerti Choudhary","Sarel Cohen","Martin Schirneck"],"author_count":5,"year":2026,"published":"2026-04-30","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2604.27966","nct_id":null,"source_url":"https://arxiv.org/abs/2604.27966","archive_url":"https://space-kitty.com/papers/arxiv:2604.27966","updated":"2026-04-30","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2604.27966","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}