  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\in 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 ${\cal O}(n^2)$ space and guarantees
${\cal O}(1)$ 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 ${\cal O}(n)$ time
which is worst-case optimal.
  - Our second data structure optimizes space at the expense of increased query
time. It takes ${\cal O}(m)$ space -- which is also the space taken by $G$. The
query time is ${\cal O}(\min(m,n c_{s,t}))$ where $c_{s,t}$ is the value of the
mincut between $s$ and $t$ in $G$. This query time is faster by a factor of
$\Omega(\min(m^{1/3},\sqrt{n}))$ compared to the best known deterministic
algorithm 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, we can distribute our ${\cal O}(n^2)$
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 \in V$.

Data Structures and Algorithms