Minimum+1 (s, t)-cuts and Dual-edge Sensitivity Oracle

Let G be a directed multi-graph on n vertices andm 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 O(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 O(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 O(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 O(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 O(1) time if there exists a minimum+1 (s, t)-cut, say (A, B), such that s, u is an element of A and v, t is an element of B; the corresponding cut can be reported in O(|B|) time. (3) Sensitivity oracle: There exists an O(n(2)) size data structure that solves the dual-edge sensitivity problem for (s, t)-mincuts. It takes O(1) time to report the capacity of a resulting (s, t)-mincut (A, B) and O(|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 (Omega) over tilde (n(2)) lower bounds on the space for the latter two problems.