2026-09-08T02:21:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26424 2026-09-05T19:42:58Z ddc:004 open_access

Simpler and Improved Replacement Path Coverings Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Schirneck, Martin derandomization fault tolerance replacement path coverings sensitivity data structures An important tool in the design of fault-tolerant graph data structures are (L,f)-replacement path coverings (RPCs). An RPC is a family 𝒢 of subgraphs of a given graph G such that, for every set F of at most f edges, there is a subfamily 𝒢_F ⊆ 𝒢 with the following properties. 1) No subgraph in 𝒢_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 𝒢_F. The covering value of the RPC is the total number |𝒢| of subgraphs. The query time is the time needed to compute the subfamily 𝒢_F given the set F. Weimann and Yuster [TALG'13] devised a randomized RPC with covering value Õ(fL^f) and query time Õ(f² L^f). This was derandomized by Karthik and Parter [TALG'24], who also reduced the query time to Õ(f² 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 Õ(fL^{f+o(1)}) and decreases the query time to Õ(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 Õ((L/f)^f L^o(1)) subgraphs and show that this is tight up to the L^o(1) term. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Martin Schirneck 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.35 urn:nbn:de:0030-drops-264243 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode