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 $\tilde{O}(f{L}^f)$. Karthik and Parter [TALG 2024] showed that $\Omega ((L/f{)}^f)$ subgraphs are necessary. Recently, Bilò, Chechik, Choudhary, Cohen, and Schirneck [ICALP 2026] devised a new approach for very small sensitivities $f=o(\log L)$ with covering value $\tilde{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 $\tilde{\Theta }(\frac{(L+f{)}^{L+f}}{L^L{f}^f})\cdot \mathsf{poly}(f)$ for the much wider range of $f=O(L)$.