# Connectivity Oracles for Graphs Subject to Vertex Failures

arXiv: https://arxiv.org/abs/1607.06865 · HTML: https://mlsanity.com/paper/1607.06865/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2016.

## Built on by (most cited first, 1 of 1)

- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)

## Abstract (arXiv)

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of d≤ dstar failed vertices in tildeO(d3) time and thereafter answers connectivity queries in O(d) time. It occupies space O(dstar mlog n). We develop a randomized Monte Carlo version of our data structure with update time tildeO(d2), query time O(d), and space tildeO(m) for any failure bound d≤ n. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge-failure connectivity oracle. Using space O(nlog2 n), d edge failures are processed in O(dlog dloglog n) time and thereafter, connectivity queries are answered in O(loglog n) time, which are correct w.h.p. Our data structures are based on a new decomposition theorem for an undirected graph G=(V,E), which is of independent interest. It states that for any terminal set Usubseteq V we can remove a set B of |U|/(s-2) vertices such that the remaining graph contains a Steiner forest for U-B with maximum degree s.