Near-Optimal Replacement Path Coverings

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 $\Omega( (L/f)^f )$ subgraphs are necessary. Recently, Bil\`o, 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 = \Omega(\log L)$ must contain $\Omega( (\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{\Theta}(\frac{(L+f)^{L+f}}{L^L f^f}) \cdot \mathsf{poly}(f)$ for the much wider range of $f = O(L)$.