Metraipolis › archive › dc_5dc49211f4d2
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition — arXiv:2609.02388
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.02388
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T05:54:21.177Z
- SHA-256 of the archived text
e3d936c40ec396e6d99a4bb2522f63787210b7a87453ccdb91c0c4b333fee009- Stable URL of this page
https://metraipolis.com/documento/dc_5dc49211f4d2
How to cite
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition — arXiv:2609.02388 — arXiv (en), https://arxiv.org/abs/2609.02388 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5dc49211f4d2 (Metraipolis archive dc_5dc49211f4d2, sha256 e3d936c40ec396e6d99a4bb2522f63787210b7a87453ccdb91c0c4b333fee009)
BibTeX
@misc{dc5dc49211f4d2,
title = {Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition — arXiv:2609.02388},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.02388},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5dc49211f4d2; sha256 e3d936c40ec396e6d99a4bb2522f63787210b7a87453ccdb91c0c4b333fee009},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02388. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $\Delta$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(m\alpha(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.02388 — 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-17T05:46:54.682Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).