Sensitivity Oracles for All-Pairs Mincuts

Let G = (V, E) be an undirected unweighted graph on n vertices and m edges. We address the problem of sensitivity oracle for all-pairs mincuts in G defined as follows. Build a compact data structure that, on receiving any pair of vertices s,t ∊ V and failure (or insertion) of any edge as query, can efficiently report the mincut between s and t after the failure (or the insertion). To the best of our knowledge, there exists no data structure for this problem which takes o(mn) space and a non-trivial query time. We present the following results. Our first data structure occupies space and guarantees query time to report the value of resulting (s, t)-mincut upon failure (or insertion) of any edge. Moreover, the set of vertices defining a resulting (s, t)-mincut after the update can be reported in time which is worst-case optimal. Our second data structure optimizes space at the expense of increased query time. It takes space–which is also the space taken by G. The query time is where cs,t is the value of the mincut between s and t in G. This query time is faster by a factor of compared to the best known deterministic algorithm [21, 26, 28] to compute a (s,t)-mincut from scratch. If we are only interested in knowing if failure (or insertion) of an edge changes the value of (s, t)-mincut for any s, t ∊ V, we can distribute our space data structure evenly among n vertices. For any failed (or inserted) edge we only require the data structures stored at its endpoints to determine if the value of (s, t)-mincut has changed for any s, t ∊ V. Moreover, using these data structures we can also output efficiently a compact encoding of all pairs of vertices whose mincut value is changed after the failure (or the insertion) of an edge.