  Let G be a directed weighted graph (DiGraph) on n vertices and m edges with
source s and sink t. An edge in G is vital if its removal reduces the capacity
of (s,t)-mincut. Since the seminal work of Ford and Fulkerson, a long line of
work has been done on computing the most vital edge and all vital edges of G.
Unfortunately, after 60 years, the existing results are for undirected or
unweighted graphs. We present the following result for DiGraph, which solves an
open problem stated by Ausiello et al.
  1. There is an algorithm that computes all vital edges as well as the most
vital edge of G using O(n) maxflow computations.
  Vital edges play a crucial role in the design of Sensitivity Oracle (SO) for
(s,t)-mincut. For directed graphs, the only existing SO is for unweighted
graphs by Picard and Queyranne. We present the first and optimal SO for
DiGraph.
  2. (a) There is an O(n) space SO that can report in O(1) time the capacity of
(s,t)-mincut and (b) an O($n^2$) space SO that can report an (s,t)-mincut in
O(n) time after failure/insertion of an edge.
  For unweighted graphs, Picard and Queyranne designed an O(m) space DAG that
stores and characterizes all mincuts for all vital edges. Conversely, there is
a set containing at most n-1 (s,t)-cuts such that at least one mincut for every
vital edge belongs to the set. We generalize these results for DiGraph.
  3. (a) There is a set containing at most n-1 (s,t)-cuts such that at least
one mincut for every vital edge is present in the set. (b) We design two
compact structures for storing and characterizing all mincuts for all vital
edges, (i) O(m) space DAG for partial characterization and (ii) O(mn) space
structure for complete characterization.
  To arrive at our results, we develop new techniques, especially a
generalization of maxflow-mincut theorem by Ford and Fulkerson, which might be
of independent interest.
