Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918489180078080 |
|---|---|
| author | Li, Xizhe Long, Yaowei Pidugu, David Saranurak, Thatchaphol Wang, Benyu |
| author_facet | Li, Xizhe Long, Yaowei Pidugu, David Saranurak, Thatchaphol Wang, Benyu |
| contents | We give an improved connectivity oracle under vertex failures. After a set of $k$ vertices fails, our oracle performs an $O(k^{6})$-time update independent of the graph size $n$, and then answers pairwise connectivity queries in optimal $O(k)$ time. For constant $k$, it uses near-linear space and can be built in near-linear preprocessing time.
In contrast, all prior oracles with $n$-independent update time[PSS+22, vdBS19] either require $Ω(n^{2})$ space or incur $2^{2^{O(k)}}$ update and query time. Moreover, their preprocessing time is polynomially large in $n$, far from near-linear.
Our oracle builds on the unbreakable decomposition framework of[PSS+22], but introduces three new ingredients: (i) shortcutting over the tree decomposition to reduce space from quadratic to near-linear, (ii) bootstrapping that leverages $n$-dependent oracles internally to obtain near-linear preprocessing, and (iii) a new patch set mechanism that yields conditionally optimal $O(k)$ query time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07168 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition Li, Xizhe Long, Yaowei Pidugu, David Saranurak, Thatchaphol Wang, Benyu Data Structures and Algorithms We give an improved connectivity oracle under vertex failures. After a set of $k$ vertices fails, our oracle performs an $O(k^{6})$-time update independent of the graph size $n$, and then answers pairwise connectivity queries in optimal $O(k)$ time. For constant $k$, it uses near-linear space and can be built in near-linear preprocessing time. In contrast, all prior oracles with $n$-independent update time[PSS+22, vdBS19] either require $Ω(n^{2})$ space or incur $2^{2^{O(k)}}$ update and query time. Moreover, their preprocessing time is polynomially large in $n$, far from near-linear. Our oracle builds on the unbreakable decomposition framework of[PSS+22], but introduces three new ingredients: (i) shortcutting over the tree decomposition to reduce space from quadratic to near-linear, (ii) bootstrapping that leverages $n$-dependent oracles internally to obtain near-linear preprocessing, and (iii) a new patch set mechanism that yields conditionally optimal $O(k)$ query time. |
| title | Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.07168 |