Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
This provides a more efficient solution for dynamic connectivity under vertex failures, a fundamental problem in graph algorithms, with practical near-linear resources for small failure sets.
The paper presents a connectivity oracle for vertex failures that achieves O(k^6) update time independent of graph size n and O(k) query time, using near-linear space and preprocessing for constant k, significantly improving over prior work with exponential overhead or quadratic space.
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.