Let G be a directed multi-graph on n vertices and m edges with a designated source vertex s and a designated sink vertex t . We study the ( s,t )-cuts of capacity minimum+1 and as an important application of them, we give a solution to the dual-edge sensitivity for ( s,t )-mincuts—reporting an ( s,t )-mincut upon failure or insertion of any pair of edges. Picard and Queyranne [Mathematical Programming Studies, 13(1): 8–16 (1980)] showed that there exists a directed acyclic graph (DAG) that compactly stores all minimum ( s,t )-cuts of G . This structure also acts as an oracle for the single-edge sensitivity of minimum ( s,t )-cut. For undirected multi-graphs, Dinitz and Nutov [STOC, 509–518 (1995)] showed that there exists an 𝒪( n ) size 2-level Cactus model that stores all global cuts of capacity minimum+1. However, for minimum+1 ( s,t )-cuts, no such compact structure exists till date. We present the following structural and algorithmic results on minimum+1 ( s,t )-cuts. (1) Structure: There is an 𝒪( m ) size 2-level DAG structure that stores all minimum+1 (s,t) -cuts of G such that each minimum+1 ( s,t )-cut appears as 3-transversal cut—it intersects any path in this structure at most thrice. We also show that there is an 𝒪( mn ) size structure for storing and characterizing all minimum+1 (s,t) -cuts in terms of 1-transversal cuts. (2) Data structure: There exists an 𝒪( n 2 ) size data structure that, given a pair of vertices {u,v} that are not separated by an ( s,t )-mincut, can determine in 𝒪(1) time if there exists a minimum+1 ( s,t )-cut, say ( A,B ), such that s,u ∊ A and v,t∊ B ; the corresponding cut can be reported in 𝒪(| B |) time. (3) Sensitivity oracle: There exists an 𝒪( n 2 ) size data structure that solves the dual-edge sensitivity problem for (s,t) -mincuts. It takes 𝒪(1) time to report the capacity of a resulting (s,t) -mincut (A,B) and 𝒪(| B |) time to report the cut. (4) Lower bounds: For the data structure problems addressed in results (2) and (3) above, we also provide a matching conditional lower bound. We establish a close relationship among three seemingly unrelated problems—all-pairs directed reachability problem, the dual-edge sensitivity problem for ( s,t )-mincuts, and the problem of reporting the capacity of ({ x,y }, { u,v })-mincut for any four vertices x,y,u,v in G . Assuming the Directed Reachability Hypothesis by Patrascu [SIAM J. Computing, 827–847 (2011)] and Goldstein et al. [WADS, 421–436 (2017)], this leads to \(\tilde{\Omega }(n^2)\) lower bounds on the space for the latter two problems.

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.