Connectivity Oracles for Graphs Subject to Vertex Failures

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.