Simpler and Improved Replacement Path Coverings

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