Metraipolis › archive › dc_e26b9cd8bc88
Near-Optimal Replacement Path Coverings — arXiv:2608.07124
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.07124
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-23T15:11:02.192Z
- SHA-256 of the archived text
a4555d6a9dd6df135d283069cf81d796c8213553a7ddfd7b0b0b8b55dddec860- Stable URL of this page
https://metraipolis.com/documento/dc_e26b9cd8bc88
How to cite
Near-Optimal Replacement Path Coverings — arXiv:2608.07124 — arXiv (en), https://arxiv.org/abs/2608.07124 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e26b9cd8bc88 (Metraipolis archive dc_e26b9cd8bc88, sha256 a4555d6a9dd6df135d283069cf81d796c8213553a7ddfd7b0b0b8b55dddec860)
BibTeX
@misc{dce26b9cd8bc88,
title = {Near-Optimal Replacement Path Coverings — arXiv:2608.07124},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.07124},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e26b9cd8bc88; sha256 a4555d6a9dd6df135d283069cf81d796c8213553a7ddfd7b0b0b8b55dddec860},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07124. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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ò, 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)$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07124 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:08:55.956Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).