Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut Surender Baswana, Koustav Bhanja, Anupam Roy Abstract Let G G be a directed graph on n n vertices and m m edges. In this paper, we study ( s , t ) (s,t) -cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1. Second (s,t)-mincut: Vazirani and Yannakakis [ICALP 1992] designed the first algorithm for computing an ( s , t ) (s,t) -cut of second minimum capacity using π’ͺ ⁑ ( n 2 ) {\mathcal{O}}(n^{2}) maximum ( s , t ) (s,t) -flow computations. We present the following algorithm that improves the running time significantly. For directed integer-weighted graphs, there is an algorithm that can compute an ( s , t ) (s,t) -cut of second minimum capacity using π’ͺ ~ ​ ( n ) {\tilde{\mathcal{O}}}(\sqrt{n}) maximum ( s , t ) (s,t) -flow computations with high probability. 1 1 1 π’ͺ ~ ( . ) \tilde{\mathcal{O}}(.) hides poly-logarithmic factors. To achieve this result, a close relationship of independent interest is established between ( s , t ) (s,t) -cuts of second minimum capacity and global mincuts in directed weighted graphs. 2. Minimum+1 (s,t)-cuts: Minimum+1 ( s , t ) (s,t) -cuts have been studied quite well recently [Baswana, Bhanja, and Pandey, ICALP 2022 & TALG 2023], which is a special case of second ( s , t ) (s,t) -mincut. We present the following structural result and the first nontrivial algorithm for minimum+1 ( s , t ) (s,t) -cuts. (a) Algorithm: For directed multi-graphs, we design an algorithm that, given any maximum ( s , t ) (s,t) -flow, computes a minimum+1 ( s , t ) (s,t) -cut, if it exists, in π’ͺ ⁑ ( m ) {\mathcal{O}}(m) time. (b) Structure: The existing structures for storing and characterizing all minimum+1 ( s , t ) (s,t) -cuts occupy π’ͺ ⁑ ( m ​ n ) {\mathcal{O}}(mn) space [Baswana, Bhanja, and Pandey, TALG 2023]. For undirected multi-graphs, we design a directed acyclic graph (DAG) occupying only π’ͺ ⁑ ( m ) {\mathcal{O}}(m) space that stores and characterizes all minimum+1 ( s , t ) (s,t) -cuts. This matches the space bound of the widely-known DAG structure for all ( s , t ) (s,t) -mincuts [Picard and Queyranne, Math. Prog. Studies 1980]. 3. Dual Edge Sensitivity Oracle: The study of minimum+1 (s,t)-cuts often turns out to be useful in designing dual edge sensitivity oracles – a compact data structure for efficiently reporting an ( s , t ) (s,t) -mincut after insertion/failure of any given pair of query edges. It has been shown recently [Bhanja, ICALP 2025] that any dual edge sensitivity oracle for ( s , t ) (s,t) -mincut in undirected multi-graphs must occupy Ξ© ⁑ ( n 2 ) {\Omega}(n^{2}) space in the worst-case irrespective of the query time. Interestingly, for simple graphs, we break this quadratic barrier while achieving a non-trivial query time as follows. There is an π’ͺ ⁑ ( n ​ n ) {\mathcal{O}}(n\sqrt{n}) space data structure that can report an ( s , t ) (s,t) -mincut in π’ͺ ⁑ ( min ⁑ { m , n ​ n } ) {\mathcal{O}}(\min\{m,n\sqrt{n}\}) time after the insertion/failure of any given pair of query edges. To arrive at our results, as one of our key techniques, we establish interesting relationships between ( s , t ) (s,t) -cuts of capacity ( ( minimum OPEN + Ξ” ) +\Delta) , Ξ” β‰₯ 0 \Delta\geq 0 , and maximum ( s , t ) (s,t) -flow. We believe that these techniques and the graph-theoretic result in 2.(b) are of independent interest. 1 Introduction The concept of cut is fundamental in graph theory and has numerous real-world applications [ AMO93 ] . Let G=(V,E) be a directed weighted graph on n=|V| vertices and m=|E| edges with a designated source vertex s and a designated sink vertex t . Every edge e of G is assigned with a non-negative real value as the capacity of the edge, denoted by w(e) . There are mainly two types of well-studied cuts in a graph – global cuts and (s,t) -cuts. A global cut , or simply a cut , of G is defined as a nonempty proper subset of V . A cut C is said to be an (s,t) -cut if s\in C and t\in\overline{C}=V\setminus C . Every cut of G is associated with a capacity defined as follows. The capacity of a cut C , denoted by c(C) , is the sum of the capacities of every edge (x,y) satisfying x\in C and y\in\overline{C} . A global cut (likewise (s,t) -cut) of the least capacity is called a global mincut (likewise (s,t) -mincut ). Henceforth \lambda denotes the capacity of (s,t) -mincut. The study of cuts from both structural and algorithmic perspectives has been an important field of research for the past six decades [ GH61 , FF56 , DKL76 , KS96 , VDBCP+23 ] . In this paper, we provide the following two main results for (s,t) -cuts. (1) We present efficient algorithms for computing an (s,t) -cut of second minimum capacity in directed weighted graphs. After more than 30 years, our algorithms provide the first improvement by a polynomial factor over the existing result of Vazirani and Yannakakis [ VY92 ] . To arrive at this result, we establish that computing an (s,t) -cut of second minimum capacity has the same time complexity as computing a global mincut. (2) We present a dual edge sensitivity oracle for (s,t) -mincut – a compact data structure that efficiently reports an (s,t) -mincut after the insertion or failure of any pair of edges. This is the first dual edge sensitivity oracle for (s,t) -mincut that occupies subquadratic space while achieving nontrivial query time in simple graphs 1 1 1 A simple graph refers to an undirected unweighted graph having no parallel edges. . This breaks the existing quadratic lower bounds [ BBP23 , Bha25 ] on the space for any dual edge sensitivity oracle for (s,t) -mincut in undirected multi-graphs 2 2 2 A multi-graph refers to an unweighted graph having parallel edges. . We arrive at this result by designing a compact structure for storing and characterizing all minimum+1 (s,t) -cuts (a special case of second minimum (s,t) -cut). This structure improves the space occupied by the existing best-known structure [ BBP23 ] by a linear factor. We now present the problems addressed in this paper, their state-of-the-art, and our results. 1.1 Faster Algorithm for Second Minimum (s,t)-cuts An algorithmic graph problem aims at computing a structure that optimizes a given function. Examples of such classical problems are Minimum Spanning Tree, Shortest Path, Minimum Cut. Having designed (near) optimal algorithm for such problems, the next immediate objective is the following. Design an efficient algorithm that, given a structure S achieving optimal function value, computes a structure S^{\prime} that differs from S and achieves the optimal or next optimal function value. There has been an extensive study on computing the second minimum spanning tree [ CFM74 , KIM81 , MP92 ] , the second shortest path [ BKH57 , Yen71 , Epp98 , Rod10 ] , and second (s,t) -mincut [ VY92 ] . The algorithms for these problems are so fundamental that they appear in textbooks on algorithms [ CLRS22 , AMO93 ] . In addition, they act as the foundation for generalizing the problem to compute k^{th} optimal structure, such as computing k^{th} minimum spanning tree, k^{th} shortest path, k^{th} (s,t) -mincut. The problem of designing efficient algorithms for computing (s,t) -mincut (or equivalently, maximum (s,t) -flow) has been studied for more than six decades. This problem is now almost settled with the recent breakthrough result on almost linear time algorithm for maximum (s,t) -flow by Van et al. [ VDBCP+23 ] . Interestingly, given an algorithm for maximum (s,t) -flow, we can compute all (s,t) -mincuts implicitly with an additional {\mathcal{O}}(m) time, as shown by Picard and Queyranne [ PQ80 ] . It is, therefore, natural to redefine the second (s,t) -mincut problem as follows. Design an algorithm that computes an (s,t) -cut of second minimum capacity. For brevity, henceforth we call (s,t) -cut of second minimum capacity by second (s,t) -mincut. Vazirani and Yannakakis [ VY92 ] addressed the problem of computing an (s,t) -cut having k^{th} minimum capacity in 1992. For computing any k^{th} minimum capacity (s,t) -cut, they gave an algorithm that uses {\mathcal{O}}(n^{2(k-1)}) maximum (s,t) -flow computations. Conversely, they also argued, using NP-hardness of computing a maximum cut, that exponential dependence on k is unavoidable assuming P\neq NP . To arrive at their result, the key problem they addressed is the design of an algorithm that computes a second (s,t) -mincut using {\mathcal{O}}(n^{2}) maximum (s,t) -flow computations. They further improve the running time by designing a faster algorithm that computes a second (s,t) -mincut using only {\mathcal{O}}(n) maximum (s,t) -flow computations. We show that this faster algorithm is incorrect due to a serious error in its analysis (refer to Section C for details). As a result, the existing best-known algorithm for computing a second (s,t) -mincut uses {\mathcal{O}}(n^{2}) maximum (s,t) -flow computations [ VY92 ] . We design an algorithm for the second (s,t) -mincut with a significantly improved running time as shown in the following theorem. Theorem 1 (Second (s,t) -mincut algorithm) . For any directed graph G on n vertices with integer edge capacities, there is an algorithm that computes a second (s,t) -mincut in G using \tilde{{\mathcal{O}}}(\sqrt{n}) maximum (s,t) -flow computations with high probability. The two well-known minimum cuts in a graph are (s,t) -mincut and global mincut. Recently, there has been a growing interest in understanding the difference in the complexity of computing an (s,t) -mincut and computing a global mincut. For undirected weighted graphs, Li and Panigrahi [ LP20 ] established that the running time of computing a global mincut differs by only poly-logarithmic factors from the running time of computing an (s,t) -mincut. In particular, the authors showed that there is an algorithm that can compute a global mincut using \tilde{{\mathcal{O}}}(1) maximum (s,t) -flow computations with additional \tilde{\mathcal{O}}(m) time. However, for directed weighted graphs, there is a large gap between the running time of computing an (s,t) -mincut and computing a global mincut as follows. Cen et al. [ CLN+21 ] designed an algorithm that can compute a global mincut using \tilde{\mathcal{O}}(\sqrt{n}) maximum (s,t) -flow computations with additional \tilde{\mathcal{O}}(m\sqrt{n}) time. Interestingly, to arrive at our result in Theorem 1 , we show that the complexity of computing a global mincut is the same as the complexity of computing a second (s,t) -mincut modulo a single maximum (s,t) -flow computation as follows, which might find many other important applications. Theorem 2 (Equivalence between global mincut and second (s,t) -mincut) . For any directed weighted graph G on n vertices and m edges, the following two assertions hold. 1. The problem of computing a second (s,t) -mincut is reducible to the problem of computing a global mincut in {\mathcal{O}}(MF(m,n)) time, where MF(m,n) denotes the time complexity for computing a maximum (s,t) -flow in G . 2. The problem of computing a global mincut is reducible to the problem of computing a second (s,t) -mincut in \mathcal{O}(m) time. Remark 1 . Our algorithm for computing a second (s,t) -mincut in Theorem 1 is Monte Carlo and works for graphs with integer edge capacities. However, the equivalence between second (s,t) -mincut and global mincut in Theorem 2 is deterministic and holds even for graphs with real edge capacities. 1.2 Minimum+1 (s,t)-cuts: Efficient Algorithm & Compact Structure The cuts of capacity minimum+1, known as minimum+1 cuts, have been studied quite extensively in the past [ BBP23 , DN95 , Bha25 ] . For (un)directed multi-graphs, a minimum+1 (s,t) -cut is a special case of second (s,t) -mincut. We present the following structural result and the first nontrivial algorithm for minimum+1 (s,t) -cuts. Algorithm: For both minimum+1 global cuts [ DN95 ] and minimum+1 (s,t) -cuts [ BBP23 ] , there exist compact data structures. These data structures have important applications in maintaining minimum+2 edge connected components [ DN95 ] and designing dual edge sensitivity oracle for (s,t) -mincut [ BBP23 ] . Moreover, there exist efficient algorithms [ Kar93 , Ben95 , NNI97 ] that can compute a global cut of capacity minimum+1. Unfortunately, the existing best-known algorithm for computing an (s,t) -cut of capacity minimum+1 is nothing but the algorithm for computing a second (s,t) -mincut by [ VY92 ] , which uses {\mathcal{O}}(n^{2}) maximum (s,t) -flow computations. We present the following result as the first efficient algorithm for computing an (s,t) -cut of capacity minimum+1 (proof is in Appendix H ). Theorem 3 (Minimum+1 (s,t) -cut algorithm) . For any directed multi-graph G on n vertices and m edges, there is an algorithm that, given any maximum (s,t) -flow, computes a minimum+1 (s,t) -cut, if exists in G , in {\mathcal{O}}(m) time. Remark 2 . The best-known algorithm for computing an (s,t) -mincut uses one maximum (s,t) -flow computation. It follows from Theorem 3 that the running time of computing a minimum+1 (s,t) -cut differs from the running time of computing an (s,t) -mincut only by additional \mathcal{O}(m) time. Structure: There are several algorithmic applications on cuts, namely, fault-tolerance [ PQ80 , DKL76 ] , dynamic algorithms [ GH23 , GHT18 ] , edge-connectivity augmentation [ NGM97 , CLP22 ] that require an efficient way to distinguish a set of cuts, say minimum cuts or minimum+1 cuts, from the rest of the cuts. A trivial way to accomplish this objective is to store each cut of the required set explicitly. However, this is totally impractical since the set of these cuts is usually quite huge. For example, the number of (s,t) -mincuts are exponential [ PQ80 ] , and the number of global mincuts are \Omega(n^{2}) [ DKL76 ] . This has led the researchers to invent the following concept. A structure H is said to characterize a set of cuts {\mathcal{C}} using a property P if the following condition holds. A cut C\in{\mathcal{C}} if and only if C satisfies property P in H . It is desirable that H is as compact as possible. Moreover, verifying if a given cut C satisfies P in H has to be as time-efficient as possible. The design of compact structures for characterizing minimum cuts started with the seminal work of Dinitz, Karzanov, and Lomonosov [ DKL76 ] in 1976. In this work, the well-known cactus graph occupying {\mathcal{O}}(n) space was invented for storing and characterizing all global mincuts. Several compact structures have been designed subsequently for storing and characterizing cuts of capacity both minimum and near minimum [ PQ80 , Ben95 , DN95 , DV00 , BBP23 ] . Quite expectedly, they are playing crucial roles in establishing many important algorithmic results [ VY92 , Ben95 , DN95 , GHT18 , KT19 , BBP23 ] . In particular, compact structures for storing and characterizing all minimum+1 cuts of a graph have been well-studied. For all minimum+1 global cuts in undirected multi-graphs, Dinitz and Nutov [ DN95 ] constructed an {\mathcal{O}}(n) space 2-level cactus model that stores and characterizes them. For all minimum+1 (s,t) -cuts in directed multi-graphs, the existing structure that provides a characterization occupies {\mathcal{O}}(mn) space [ BBP23 ] . Unfortunately, the space occupied by this structure of [ BBP23 ] is significantly inferior to the widely-known {\mathcal{O}}(m) space directed acyclic graph (DAG) of Picard and Queyranne [ PQ80 ] , which stores and characterizes all (s,t) -mincuts using 1 -transversal cuts. An (s,t) -cut is said to be 1 -transversal if its edge-set 3 3 3 The edge-set of a cut C is the set of edges with exactly one endpoint in C . intersects any path at most once. Interestingly, we are able to achieve the {\mathcal{O}}(m) bound on space for storing and characterizing all minimum+1 (s,t) -cuts. An edge (u,v) is said to contribute to a cut C if u\in C and v\in\overline{C} . We first establish that for any maximum (s,t) -flow f , there exists a set containing at most n-2 edges, called the anchor edges, such that for any minimum+1 (s,t) -cut C , exactly one anchor edge contributes to C . By exploiting this result, we design the following structure for storing and characterizing all minimum+1 (s,t) -cuts. Theorem 4 (Structure for minimum+1 (s,t)-cuts) . Let G be an undirected multi-graph on n vertices and m edges with a maximum (s,t) -flow f . There is an {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space structure, consisting of a directed acyclic graph {\mathcal{D}} and the set of n-2 anchor edges, that stores and characterizes all (s,t) -mincuts and all minimum+1 (s,t) -cuts of G as follows. 1. An (s,t) -cut C is an (s,t) -mincut in G if and only if C is a 1 -transversal cut in {\mathcal{D}} to which no anchor edge corresponding to f contributes. 2. An (s,t) -cut C is a minimum+1 (s,t) -cut in G if and only if C is a 1 -transversal cut in {\mathcal{D}} to which exactly one anchor edge corresponding to f contributes. For undirected graphs, the best-known structure for storing and characterizing all (s,t) -mincuts is the DAG of Picard and Queyranne [ PQ80 ] that occupies {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space, which is tight as well (refer to [ GY95 ] and Lemma 12 in [ GH23 ] ). Interestingly, not only our structure in Theorem 4 matches the bound on space with the DAG for (s,t) -mincuts [ PQ80 ] but also it stores and characterizes both (s,t) -mincuts and minimum+1 (s,t) -cuts. 1.3 Dual Edge Sensitivity Oracle: Breaking the Quadratic Barrier The study of minimum+1 (s,t) -cuts often turns out to be useful in designing elegant dual edge sensitivity oracles [ BBP23 , DN95 , Bha25 ] , which is defined as follows. Definition 1 (Dual edge sensitivity oracle) . A dual edge sensitivity oracle for minimum cuts is a compact data structure that can efficiently report a minimum cut in the graph after the insertion or failure of any given pair of query edges. Designing sensitivity oracles for various minimum cuts of a graph has been an emerging field of research [ PQ80 , CH91 , DN95 , DV00 , BGK22 , BP22 , BBP23 , BB24 ] For (s,t) -mincut in multi-graphs, the DAG structure of Picard and Queyranne [ PQ80 ] , as shown in [ BBP23 ] , can be used to design an {\mathcal{O}}(n) space sensitivity oracle that can report an (s,t) -mincut in {\mathcal{O}}(n) time after the failure/insertion of any single edge. It is now interesting to design a sensitivity oracle that can handle multiple failures/insertions of edges. To solve this generic problem, as argued in [ BBP23 ] , the natural approach is to first design a dual edge sensitivity oracle for (s,t) -mincut. This approach has also been taken for various other classical graph problems, including distance and connectivity [ DP09 ] , graph traversals [ Par15 ] , reachability [ Cho16 , CC20 ] . Moreover, it has been observed that handling two edge failures/insertions is significantly more nontrivial than handling a single one. It also provides important insights that either expose the hardness or help in generalizing the problem for multiple failures. In order to extend the result of [ PQ80 ] from single to multiple edge failures/insertions, Baswana, Bhanja, and Pandey [ BBP23 ] designed the first dual edge sensitivity oracle for (s,t) -mincut occupying {\mathcal{O}}(n^{2}) space in (un)directed multi-graphs. It can report a resulting (s,t) -mincut in {\mathcal{O}}(n) time. Note that quadratic space data structures often pose practical challenges as n can be quite large for the real world networks/graphs. It thus raises the need to design sensitivity oracles for various fundamental graph problems that occupy subquadratic space [ BCC+24 , TZ05 , Bha24 ] . Unfortunately, it has been shown [ BBP23 , Bha25 ] that any dual edge sensitivity oracle for (s,t) -mincut in undirected multi-graphs must occupy \Omega(n^{2}) bits of space in the worst case, irrespective of the query time. However, for simple graphs, we break this quadratic barrier on the space of any dual edge sensitivity oracle while achieving nontrivial query time as follows. Theorem 5 (Dual edge sensitivity oracle for (s,t) -mincut) . Let G be a simple graph on n vertices and m edges. There exists a data structure occupying {\mathcal{O}}(\min\{m,n^{1.5}\}) space that can report an (s,t) -mincut C (including the contributing edges of C ) in {\mathcal{O}}(\min\{m,n^{1.5}\}) time after the failure or insertion of any given pair of query edges in G . For the existing dual edge sensitivity oracles for (s,t) -mincut [ BBP23 , Bha25 ] , no nontrivial preprocessing time is known till date. We establish the following almost linear preprocessing time for our dual edge sensitivity oracle in Theorem 5 . Theorem 6 (Preprocessing time) . For simple graphs on n vertices and m edges, there is an algorithm that, given any maximum (s,t) -flow, can construct the dual edge sensitivity oracle in Theorem 5 in {\mathcal{O}}(m) time. 2 Organization of this Paper This paper is organized as follows. Basic preliminaries and notations are in Section 3 . A detailed overview of our results and the techniques used to arrive at them is provided in Section 4 . The full version, containing all the omitted proofs, is provided in the appendix, starting from Appendix A . 3 Preliminaries By integrality of maximum (s,t) -flow [ FF56 ] , for integer-weighted graphs, we consider any given maximum (s,t) -flow to be integral. The following notations to be used throughout the paper. β€’ G\cup A (likewise G\setminus A ): Graph obtained after adding (likewise removing) a set of edges A in G . β€’ (\lambda+\Delta) (s,t) -cut: An (s,t) -cut of capacity \lambda+\Delta where \Delta\geq 0 . β€’ (u,v) -path : A simple directed path from vertex u to vertex v . β€’ f denotes a maximum (s,t) -flow in graph G . β€’ c(C,H) : Capacity of a cut C in a graph H . β€’ A cut C subdivides a set of vertices X if C\cap X\neq\emptyset and \overline{C}\cap X\neq\emptyset . β€’ A cut C separates a pair of vertices u,v if u\in C and v\in\overline{C} or vice-versa. β€’ The edge-set of a cut C , denoted by E(C) , is the set of all edges whose endpoints are separated by C . Let f^{\prime} be any (s,t) -flow in G . β€’ H^{f^{\prime}} denotes the residual graph for any graph H corresponding to an (s,t) -flow f^{\prime} . β€’ f^{\prime}(e) denotes the value of flow f^{\prime} assigned to an edge e . β€’ f^{\prime}_{out}(C) and f^{\prime}_{in}(C) : For any (s,t) -cut C , f^{\prime}_{out}(C) (likewise f^{\prime}_{in}(C) ) is the sum of flow assigned to all edges e=(u,v)\in E(C) with u\in C,v\in\overline{C} (likewise v\in C,u\in\overline{C} ). Lemma 1 (Conservation of flow) . For any (s,t) -cut C , f^{\prime}_{out}(C)-f^{\prime}_{in}(C)=value(f^{\prime}) Lemma 2 (Sub-modularity of Cuts) . For any C_{1},C_{2}\subseteq V , c(C_{1})+c(C_{2})\geq c(C_{1}\cup C_{2})+c(C_{1}\cap C_{2}) Definition 2 (Quotient Graph) . A graph H is said to be a quotient graph of G if H is obtained from G by contracting disjoint subsets of vertices into single nodes. Definition 3 (Quotient Path) . A path P_{q} is said to be a quotient path of a path P if P_{q} is obtained from P by contracting a set of edges in P . Residual graph for undirected multi-graphs: Although the residual graph is defined for directed graphs [ FF56 ] , for undirected graphs, we define the residual graph in the following way. Let e=(x,y) be any edge in an undirected multi-graph H with an (s,t) -flow f^{\prime} . There exist two edges (y,x) (likewise (x,y) ) in H^{f^{\prime}} if e carries flow in the direction x to y (likewise y to x ); otherwise, there is a pair of edges (x,y) and (y,x) in H^{f^{\prime}} . 3.1 A DAG structure for storing and characterizing all (s,t) -mincuts In a seminal work, Picard and Queyranne [ PQ80 ] designed a DAG, denoted by \mathcal{D}_{PQ}(G) , that stores all (s,t) -mincuts in G and characterizes them as 1 -transversal cuts. We now briefly describe the construction of \mathcal{D}_{PQ}(G) . Construction of \mathcal{D}_{PQ}(G): Let G^{\prime} be the graph obtained by contracting each Strongly Connected Component (SCC) of G^{f} into a single node. Let \mathbb{T} denote the node containing t and \mathbb{S} denote the node containing s in G^{\prime} . If G is an undirected graph, \mathcal{D}_{PQ}(G) is the graph G^{\prime} . For directed graphs, \mathcal{D}_{PQ}(G) is obtained by suitably modifying G^{\prime} as follows. For each node \mu reachable from \mathbb{S} in G^{\prime} , \mu is contracted into node \mathbb{S} . Likewise, each node \mu that has a path to \mathbb{T} , is contracted into the node \mathbb{T} . Given any maximum (s,t) -flow f , \mathcal{D}_{PQ}(G) can be obtained in \mathcal{O}(m) time and has the following property. Without causing ambiguity, we refer ({\mathbb{S}},{\mathbb{T}}) -cut in {\mathcal{D}}_{PQ}(G) by (s,t) -cut. Theorem 7 ( [ PQ80 ] ) . Let G be any directed weighted graph on m edges with a designated source vertex s and designated sink vertex t . There is an {\mathcal{O}}(m) space DAG {\mathcal{D}}_{PQ}(G) that stores and characterizes each (s,t) -mincut in G as follows. An (s,t) -cut C is an (s,t) -mincut in G if and only if C is a 1 -transversal cut in {\mathcal{D}}_{PQ}(G) . Let V(\mu) denote the vertices mapped to a node \mu in \mathcal{D}_{PQ}(G) . A cut C is said to subdivide a node \mu in \mathcal{D}_{PQ}(G) if C subdivides V(\mu) . It follows from Theorem 7 that any (s,t) -cut in G that subdivides a node in \mathcal{D}_{PQ}(G) has capacity strictly greater than \lambda . Hence, the following lemma is immediate. Lemma 3 . For any pair of vertices u,v\in V , u and v are mapped to the same node in \mathcal{D}_{PQ}(G) if and only if u and v are not separated by any (s,t) -mincut in G . It is immediate from Lemma 3 and Definition 2 that {\mathcal{D}}_{PQ}(G) is a quotient graph of G . 4 An Overview of Our Results and Techniques We now present an overview of our results and the new techniques applied to arrive at them. 4.1 Faster Algorithm for Second (s,t)-mincut We design two efficient algorithms for computing a second (s,t) -mincut. Our first algorithm computes a second (s,t) -mincut for directed weighted graphs using {\mathcal{O}}(n) maximum (s,t) -flow computations, which achieves the aim of Vazirani and Yannakakis [ VY92 ] . This algorithm can be seen as an immediate application of the recently invented covering technique of [ BBP23 ] . Our second algorithm takes a totally different approach. This approach is based on a relationship between the second (s,t) -mincuts and the global mincuts in directed weighted graphs. So, as our main result, we design an algorithm for computing a second (s,t) -mincut that uses \tilde{{\mathcal{O}}}(\sqrt{n}) maximum (s,t) -flow computations and works for directed graphs with integer edge capacities. We now provide an overview of this result. Observe that a global mincut is not necessarily an (s,t) -cut in G . On the other hand, any second (s,t) -mincut can never be a global mincut in G . So apparently there does not seem to be any relationship between the global mincuts and the second (s,t) -mincuts of G . Let us first work with a special case when graph G has exactly two (s,t) -mincuts – \{s\} and V\setminus\{t\} . Suppose there exists a second (s,t) -mincut C in graph G such that C separates all the neighbors of s from all the neighbors of t . It is easy to compute a second (s,t) -mincut in this graph as follows. Compute a maximum (s,t) -flow after contracting all neighbors of s with s and all neighbors of t with t . The challenge arises when every second (s,t) -mincut has at least one contributing edge that is incident on s and/or t . We now show that the residual graph G^{f} plays a crucial role in overcoming this hurdle. Moreover, G^{f} turns out to establish the bridge between second (s,t) -mincuts and global mincuts. We begin by stating the following property, which is immediate from the Maxflow-Mincut Theorem. Property 1 . For any graph \mathbb{G} with maximum (s,t) -flow f^{\prime} , every (s,t) -mincut in \mathbb{G} is an (s,t) -cut of capacity zero in \mathbb{G}^{f^{\prime}} . It follows from Property 1 that there is a bijective mapping between the set of all (s,t) -mincuts in G and the set of global mincuts containing s and not t in G^{f} . However, Property 1 does not reveal any information on how a second (s,t) -mincut in G appears in residual graph G^{f} . To explore the structure of second (s,t) -mincuts in G^{f} , using only the conservation of flow (Lemma 1 ) and the construction of the residual graph, we provide a generalization of Property 1 as follows (refer to Theorem 10 in full version). Property 2 . For any graph \mathbb{G} with maximum (s,t) -flow f^{\prime} , every (s,t) -cut of capacity \lambda+\Delta in \mathbb{G} appears as an (s,t) -cut of capacity \Delta in \mathbb{G}^{f^{\prime}} , where \Delta\geq 0 . It follows from Property 2 that every second (s,t) -mincut in G is a second (s,t) -mincut in G^{f} . Let the capacity of second (s,t) -mincut in G be \lambda+\Delta_{2} , where \Delta_{2}>0 . Recall that our aim is to establish a relationship between second (s,t) -mincuts and global mincuts using G^{f} . So, by Property 2 , we need to focus on global cuts of capacity exactly \Delta_{2} in G^{f} . However, observe that a global cut of capacity \Delta_{2} can never be a global mincut in G^{f} since \Delta_{2}>0 . Moreover, there may exist many global cuts of capacity \Delta_{2} that cannot be a second (s,t) -mincut in G . It is observed that a directed graph has global mincut capacity strictly greater than zero if it is an SCC. It turns out that there is exactly one nontrivial SCC, say H , in the residual graph G^{f} since G has exactly two trivial (s,t) -mincuts. By exploiting Property 1 and 2 , we immediately arrive at the following inequality. The capacity of second (s,t) -mincut in G \geq \lambda+ the capacity of global mincut in H (1) Now, we establish the converse of Inequality 1 . Let us consider any global mincut A in H . Observe that A is not a second (s,t) -mincut in G^{f} since s,t\in\overline{A} . In fact, the capacity of any global cut A in H might be strictly less than the capacity of A in G^{f} . This is because of the existence of edges that are incident on s and/or t , which may contribute to A in G^{f} . Interestingly, exploiting the structure of G^{f} , the properties of SCC H , and Inequality 1 , we achieve the following bijective mapping (refer to Lemma 9 in full version). Property 3 . Let C_{1} be a global mincut in H and C_{2} be a second (s,t) -mincut in G . Then, 1. capacity of C_{2} in G =\lambda+ the capacity of C_{1} in H and 2. C_{1}\cup\{s\} is a second (s,t) -mincut in G and C_{2}\setminus\{s\} is a global mincut in H . It turns out that Property 3 does not immediately hold for graphs with one or more than two (s,t) -mincuts. For graphs with exactly one (s,t) -mincut, we suitably modify the SCC H in G^{f} . Finally, by crucially exploiting the structural properties of the DAG \mathcal{D}_{PQ}(G) (Theorem 7 ), we extend our results to general graphs having any number of (s,t) -mincuts. This leads to Theorem 2 (1). The proof of Theorem 2 (2) is straightforward using standard techniques. Cen et al. [ CLN+21 ] recently designed an efficient algorithm for computing a global mincut in directed graphs with integer edge capacities. Their algorithm uses \tilde{{\mathcal{O}}}(\sqrt{n}) maximum (s,t) -flow computations to compute a global mincut. This result of Cen et al. [ CLN+21 ] , along with Theorem 2 , immediately leads to Theorem 1 . 4.2 Compact Structure for All Minimum+1 (s,t) -cuts We address the following problem for undirected multi-graphs in this section. Problem 1 . Design a compact structure for storing and characterizing all (\lambda+1) (s,t) -cuts. To solve Problem 1 , we establish the following flow-based characterization of (\lambda+1) (s,t) -cuts, which is of independent interest. Flow based characterization of (\lambda+1) ( s,t )-cuts: In a seminal work in 1956, Ford and Fulkerson [ FF56 ] established a strong duality between (s,t) -mincut and maximum (s,t) -flow, which is widely known as the Maxflow-Mincut Theorem . This theorem provides a characterization of all (s,t) -mincuts using a maximum (s,t) -flow. However, it seems that any extension of this result might not exist for characterizing (s,t) -cuts of capacity \lambda+1 . This is because no equivalent (s,t) -flow is known corresponding to a (\lambda+1) (s,t) -cut, as stated in [ BBP23 ] . Interestingly, we show that, in fact, there exist close relationships between maximum (s,t) -flow and (\lambda+1) (s,t) -cuts as follows. Property 4 (refer to Theorem 9 in full version) . For any undirected multi-graph G with a maximum (s,t) -flow f , an (s,t) -cut C is a (\lambda+1) (s,t) -cut in G if and only if there is exactly one edge e in the edge-set of C such that f(e)=0 . Our Solution to Problem 1 : The problem of designing a compact structure for storing and characterizing all (s,t) -mincuts immediately reduces to Problem 1 by modifying the given graph as follows. Add a dummy source s^{\prime} (likewise a dummy sink t^{\prime} ) with \lambda-1 edges from s^{\prime} to s (likewise t to t^{\prime} ). Interestingly, for directed multi-graphs, Baswana, Bhanja, and Pandey [ BBP23 ] provide a solution to Problem 1 by essentially reducing it to the problem of designing a compact structure for storing and characterizing all (s,t) -mincuts. However, their structure occupies \mathcal{O}(mn) space. For undirected multi-graphs, we present a structure for storing and characterizing all (\lambda+1) (s,t) -cuts that occupies \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) space as follows. We construct a graph G^{\prime} such that every (\lambda+1) (s,t) -cut of G appears as an (s,t) -mincut in G^{\prime} . This will help us store and characterize all (\lambda+1) (s,t) -cuts of G using a structure that stores and characterizes all (s,t) -mincuts in G^{\prime} . To achieve this objective, we pursue the following simple idea – remove one edge from every (\lambda+1) (s,t) -cut. A naive implementation of this idea might not work as follows. There may be a pair of edges e,e^{\prime} contributing to the cut C_{1}\cap C_{2} defined by the intersection of two (\lambda+1) (s,t) -cuts C_{1},C_{2} . Even if none of the edges e,e^{\prime} contribute to both C_{1} and C_{2} , their removal will reduce the (s,t) -mincut capacity if c(C_{1}\cap C_{2}) is \lambda or \lambda+1 (refer to Figure 1 ). Figure 1 : C_{1}\cap C_{2} has capacity less than that of (s,t) -mincut after removal of e,e^{\prime} . In order to materialize the idea, we exploit 4 . This property motivates us to define a set of edges with respect to (\lambda+1) (s,t) -cuts in the following way. Anchor Edges: An edge is said to be an anchor edge if it does not carry flow in f and contributes to a (\lambda+1) (s,t) -cut. By Maxflow-Mincut Theorem, the removal of a set of edges carrying no flow in f does not reduce the capacity of (s,t) -mincut. Moreover, by 4 , for every (\lambda+1) (s,t) -cut C in G , exactly one anchor edge contributes to C . Hence, every (\lambda+1) (s,t) -cut, as well as (s,t) -mincut in G , appears as an (s,t) -mincut of capacity \lambda in G\setminus\mathcal{A} . It is also easy to observe that there may exist (s,t) -cuts with capacity more than \lambda+1 appearing as (s,t) -mincuts in G\setminus{\mathcal{A}} . However, using anchor edges {\mathcal{A}} , we can distinguish the (\lambda+1) (s,t) -cuts as follows. Property 5 . An (s,t) -cut C is a (\lambda+1) (s,t) -cut in G if and only if C is an (s,t) -mincut in G\setminus\mathcal{A} and exactly one edge from \mathcal{A} contributes to C . By Property 5 , our compact structure consists of set of edges \mathcal{A} and a structure that stores and characterizes all (s,t) -mincuts in G\setminus\mathcal{A} . It follows that the space occupied by our structure exceeds that of any structure for storing and characterizing all (s,t) -mincuts only by the size of {\mathcal{A}} . Therefore, we need to show that the set \mathcal{A} is small . Note that there exist graphs where the number of edges carrying zero flow in a given maximum (s,t) -flow can be \Omega(n^{2}) edges. However, it turns out that the cardinality of set \mathcal{A} is always \mathcal{O}(n) for any given maximum (s,t) -flow f in G . This is because of the following structural property of anchor edges. Any cycle defined by a set of edges carrying zero flow in f , cannot contain any anchor edge (refer to Lemma 23 in full version). Finally, using the best-known structure \mathcal{D}_{PQ} for storing and characterizing all (s,t) -mincuts [ PQ80 ] , we show that \mathcal{D}_{PQ}(G\setminus\mathcal{A}) occupies \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) space, which leads to Theorem 4 . Remark 3 . We also show that set \mathcal{A} can be obtained in \mathcal{O}(m) time (refer to Appendix I ). So, the space bound and preprocessing time of our structure (Theorem 4 ) match that of the best-known structure for storing and characterizing all (s,t) -mincuts [ PQ80 ] . 4.3 Dual Edge Sensitivity Oracle: Breaking the Quadratic Barrier In this section, for simple graphs, we design a subquadratic space data structure that can efficiently answer the query: report an (s,t) -mincut after the failure/insertion of any pair of edges. We assume G to be a simple graph in this section. We provide an overview for handling failure of edges in G , and handling insertion of edges is along similar lines (refer to Appendix G ). Henceforth, let e_{1}=(x_{1},y_{1}) and e_{2}=(x_{2},y_{2}) be the two failed edges in G . There is a folklore result that the residual graph G^{f} acts as an \mathcal{O}(m) space dual edge sensitivity oracle for (s,t) -mincut that achieves \mathcal{O}(m) query time. The query algorithm is derived from the augmenting path based algorithm for computing maximum (s,t) -flow by Ford and Fulkerson [ FF56 ] (briefly explained as a warm-up below). However, it is known that the residual graph occupies quadratic space if m=\Omega(n^{2}) . To design a subquadratic space dual edge sensitivity oracle for simple graphs, instead of the residual graph G^{f} , we work with our compact structure, consisting of \mathcal{D} and the set {\mathcal{A}} of anchor edges, from Theorem 4 . Recall that {\mathcal{D}}\cup{\mathcal{A}} is just a quotient graph of G^{f} , and hence, it may fail to preserve the complete information of every path in G^{f} . Even after having this incomplete information, we show that {\mathcal{D}}\cup{\mathcal{A}} is still sufficient to answer dual edge failure queries using the same algorithm used for the folklore result using residual graph G^{f} . Warm-up with residual graph: Observe that if none of the failed edges e_{1},e_{2} carry flow in maximum (s,t) -flow f then the capacity of (s,t) -mincut remains unchanged in G\setminus\{e_{1},e_{2}\} . Henceforth, we assume that edge e_{1} always carries flow in the direction from x_{1} to y_{1} . It follows from the construction of residual graph that there must exist a (t,s) -path P in G^{f} containing edge (y_{1},x_{1}) . We first reduce the flow in G using P in G^{f} , and then remove the edges (x_{1},y_{1}) and (y_{1},x_{1}) from G^{f} . Finally, using the concept of augmenting paths [ FF56 ] in residual graph, we can verify in {\mathcal{O}}(m) time whether the value of maximum (s,t) -flow becomes \lambda-1 or remains \lambda in G\setminus\{e_{1}\} . In the residual graph corresponding to the obtained maximum (s,t) -flow in G\setminus\{e_{1}\} , repeat the same procedure for edge e_{2} to verify whether edge e_{2} reduces the capacity of (s,t) -mincut in G\setminus\{e_{1}\} . This helps in reporting an (s,t) -mincut in the graph G\setminus\{e_{1},e_{1}\} in {\cal O}(m) time. Complete details are in Appendix F.1 . Our solution using {\mathcal{D}}\cup{\mathcal{A}} : We now use the structure {\mathcal{D}}\cup{\mathcal{A}} from Theorem 4 as a subquadratic space dual edge sensitivity oracle. {\mathcal{D}}_{PQ}(G) ( Theorem 7 ) can be used to design a single edge sensitivity oracle that occupies {\mathcal{O}}(n) space [ PQ80 , BBP23 ] . As observed by Baswana, Bhanja, and Pandey [ BBP23 ] , {\mathcal{D}}_{PQ}(G) can also handle dual edge failures for the special case when both failed edges contribute to only (s,t) -mincuts, using its reachability information. However, for handling any dual edge failures, the main difficulty arises when endpoints of both edges are mapped to the same node in {\mathcal{D}}_{PQ}(G) [ BBP23 ] . Our structure {\mathcal{D}}\cup{\mathcal{A}} addresses this difficulty seamlessly by first ensuring the following condition. The capacity of (s,t) -mincut changes only if the endpoints of at least one failed edge appear in different nodes of {\mathcal{D}} . This is achieved using the following property of \mathcal{D} . Property 6 (refer to Lemma 24 in full version) . Any (s,t) -cut separating a pair of vertices mapped to the same node in {\mathcal{D}} must have capacity at least \lambda+2 . Henceforth, we assume without loss of generality that endpoints of edge e_{1} appear in different nodes in {\mathcal{D}} . Let us first handle the failure of edge e_{1} . It turns out that {\mathcal{D}}\cup{\mathcal{A}} can easily report an (s,t) -mincut in G\setminus\{e_{1}\} . This exploits the following mapping of paths between G^{f} and {\mathcal{D}}\cup{\mathcal{A}} . Property 7 (refer to Lemma 29 in full version) . Let u,v be any pair of vertices mapped to different nodes \mu and \nu in \mathcal{D} . There exists an (u,v) -path P in G^{f} if and only if there exists a (\mu,\nu) -path P_{q} in \mathcal{D}\cup\mathcal{A} . Moreover, path P_{q} is a quotient path of P . We establish Property 7 by using the fact that graph {\mathcal{D}}\cup{\mathcal{A}} is a quotient graph of G^{f} by construction. Let D_{1} be the graph obtained from {\mathcal{D}}\cup{\mathcal{A}} after applying the query algorithm (described above) on {\mathcal{D}}\cup{\mathcal{A}} for the failure of edge e_{1} . By following the mapping of paths in 7 , let f_{1} be the corresponding maximum (s,t) -flow in G\setminus\{e_{1}\} and G^{f_{1}} denote the corresponding residual graph. On a high level, our technical contribution lies in showing that even after handling failure of e_{1} , D_{1} still preserves enough information about augmenting paths in G^{f_{1}} that facilitates the handling of the failure of edge e_{2} in G\setminus\{e_{1}\} . We now provide the overview. To handle the failure of edge e_{2} , the obtained graph D_{1} must satisfy the following property, which actually holds between graphs {\mathcal{D}}\cup{\mathcal{A}} and G^{f} (refer to 6 ). Property 8 (refer to Lemma 31 in full version) . D_{1} is a quotient graph of G^{f_{1}} , and the mapping of paths between them is as follows. For every path P in D_{1} , there is a path P_{1} in G^{f_{1}} such that P is a quotient path of P_{1} . In order to establish 8 , the challenging case appears when the (s,t) -mincut remains unchanged after the failure of e_{1} . In this case, let us first observe the change in the residual graph after reducing the flow that was passing through edge e_{1} . In the resulting residual graph, the query algorithm finds a path P from s to t , and flips the direction of every edge belonging to it. A similar update is executed by the query algorithm using a path P_{1} in graph {\mathcal{D}}\cup{\mathcal{A}} , where P_{1} is a quotient path of P . This could lead to the following scenario for the resulting graph D_{1} . There is a path P_{uv} in D_{1} , but there is no path P_{uv}^{r} in G^{f_{1}} such that P_{uv} is a quotient path of P_{uv}^{r} . In other words, 8 may fail to hold. So, we might report an incorrect (s,t) -mincut in G\setminus\{e_{1},e_{2}\} . Interestingly, exploiting the SCC structure of G^{f_{1}} , the structure of {\mathcal{D}} , and 6 , we ensure that such a scenario never occurs. This allows us to handle the failure of e_{2} using D_{1} exactly in the same way as handling the failure of e_{1} using {\mathcal{D}}\cup\mathcal{A} (refer to Lemma 33 in full version). This leads to Theorem 5 . Appendix A Organization of the Full Version The full version of this paper is organized as follows. In Appendix B , we establish close relationships between maximum (s,t) -flow and (s,t) -cuts of capacity beyond (s,t) -mincut, which are used as tools to arrive at the results in following sections. A limitation of an existing algorithm in [ VY92 ] for computing second (s,t) -mincut is provided in Section C . We present two algorithms for computing a second (s,t)-mincut in directed weighted graphs in Appendix D . For undirected multi-graphs, Appendix E contains the design of our linear space structure for storing and characterizing all (\lambda+1) (s,t) -cuts. Finally, in Appendix F , we design the subquadratic space dual edge sensitivity oracle for (s,t) -mincut in simple graphs using the structure constructed in Appendix E . Appendix B Minimum+k (s,t)-cuts and Maximum (s,t)-flow Ford and Fulkerson [ FF56 ] established the following strong duality between an (s,t) -mincut and a maximum (s,t) -flow. Theorem 8 ( Maxflow-Mincut Theorem [ FF56 ] ) . Let f be any maximum (s,t) -flow in G . An (s,t) -cut C in G is an (s,t) -mincut if and only if for every edge e\in E(C) , f(e)=w(e) if e is an outgoing edge of C and f(e)=0 if e is an incoming edge of C in G . In this section, as an extension to Theorem 8 , we establish the following two results. We first establish a characterization of all (\lambda+1) (s,t) -cuts based on a maximum (s,t) -flow, which holds only in undirected multi-graphs. Secondly, for directed weighted graphs, we show that for a maximum (s,t) -flow f , there exists an equivalence between the capacity of an (s,t) -cut in G and in G^{f} . B.1 Undirected Multi-Graphs For undirected multi-graphs, we establish the following property for (\lambda+k) (s,t) -cuts, where k\geq 0 is an integer, based on a maximum (s,t) -flow. Lemma 4 . Let C be a (\lambda+k) (s,t) -cut in G , where k\geq 0 is an integer. Let f be any maximum (s,t) -flow in G and let {\mathcal{E}}\subseteq E(C) be the set of edges such that f(e)=0 for every edge e\in{\mathcal{E}} . Then, 1. |{\mathcal{E}}|\leq k , 2. |{\mathcal{E}}| is odd if and only if k is odd. Proof. Suppose C is a (\lambda+k) (s,t) -cut in G . It follows from conservation of flow (Lemma 1 ), f_{out}(C)\geq\lambda , since f is a maximum (s,t) -flow and f_{in}(C)\geq 0 . Let f_{out}(C)=\lambda+j , for any integer j\geq 0 . Again by Lemma 1 , f_{in}(C)=j . Therefore, we arrive at the following equation. f_{out}(C)+f_{in}(C)=\lambda+2j (2) It follows from Equation 2 that there are exactly \lambda+2j edges belonging to E(C) that are carrying flow. Let {\mathcal{E}}\subseteq E(C) be the set of remaining edges such that, for every edge e\in{\mathcal{E}} , f(e)=0 . In undirected graphs, every edge belonging to the edge-set of a cut is a contributing edge of the cut. Therefore, using Equation 2 , we arrive at the following equality. \displaystyle\begin{split}|{\mathcal{E}}|&=c(C)-(f_{out}(C)+f_{in}(C))\\ &=\lambda+k-(\lambda+2j)\\ &=k-2j\end{split} (3) It follows from Equation 3 that |{\mathcal{E}}|\leq k . In addition, since 2j is always an even number, this implies that |{\mathcal{E}}| is odd if k is odd; otherwise |\mathcal{E}| is even. ∎ By crucially exploiting Lemma 4 , we now establish an interesting flow-based characterization of all the (\lambda+1) (s,t) -cuts. Theorem 9 (Maxflow (Min+1)-cut Theorem) . Let G be an undirected multi-graph with a designated source s and a designated sink t . Let f be any maximum (s,t) -flow in G . Then, an (s,t) -cut C in G is a (\lambda+1) (s,t) -cut if and only if there exists exactly one edge e\in E(C) such that 1. f(e)=0 and 2. for every edge e^{\prime}\in E(C)\setminus\{e\} , f(e^{\prime})=1 and e^{\prime} carries flow in the direction C to \overline{C} . Proof. Suppose C is a (\lambda+1) (s,t) -cut. Let {\mathcal{E}}\subseteq E(C) be the set of edges such that f(e)=0 for each edge e\in{\mathcal{E}} . By assigning the value of k=1 in Lemma 4 , we have |{\mathcal{E}}|\leq 1 and |{\mathcal{E}}| is odd. Since |{\mathcal{E}}| is odd, therefore, |{\mathcal{E}}|=1 . Since f is a maximum (s,t) -flow, by Lemma 1 , f_{out}(C)\geq\lambda . Moreover, we have |E(C)|=\lambda+1 . Therefore, for every edge e^{\prime}\in E(C)\setminus\{e\} , f(e^{\prime})=1 and e^{\prime} carries flow in the direction C to \overline{C} . We now prove the converse part. Suppose C is an (s,t) -cut satisfying properties (1) and (2). It follows that there is no edge e^{\prime}\in E(C) such that f(e^{\prime})=1 and carries flow in the direction \overline{C} to C . So, f_{in}(C)=0 . By using Lemma 1 , we have f_{out}(C)=\lambda . So, in E(C) , there are exactly \lambda edges that are carrying flow and exactly one edge that is carrying no flow. Therefore, |E(C)|=\lambda+1 . ∎ Figure 2 : A colored edge represents that the edge carries flow and \lambda=2 . (i) Example showing that Theorem 9 cannot be generalized for k\geq 2 ( ii ) Cut C is a (\lambda+1) (s,t) -cut with k=1 where each edge belonging to E(C) carries flow. So, |\cal E| is even although k is odd. Remark 4 . An immediate generalization of Theorem 9 would be the following. An (s,t) -cut C is a (\lambda+k) (s,t) -cut if and only if there are exactly k edges in E(C) that carry zero flow and every other edge carries flow in the direction C to \overline{C} . However, Figure 2 (i) shows that for \lambda=2 , (s,t) -cut C has capacity k+2 but there are k-2 edges in E(C) carrying zero flow. Hence, this generalization of Theorem 9 is not possible for any k\geq 2 . B.2 Directed Weighted Graphs For directed graphs, Lemma 4 (2) , as well as Theorem 9 , does not necessarily hold. This is because there exist edges incoming to a cut in directed graphs, and hence, Equation 3 fails to satisfy. (refer to Figure 2 (ii) ). Observe that the following lemma immediately follows from the Theorem 8 (Maxflow-Mincut Theorem). Lemma 5 . For any maximum (s,t) -flow f , an (s,t) -cut C is an (s,t) -mincut if and only if the capacity of C is 0 in the corresponding residual graph G^{f} . Interestingly, for directed weighted graphs, the result in Lemma 5 can be extended to (\lambda+\Delta) (s,t) -cuts, where \Delta\geq 0 as shown in the following theorem. Theorem 10 ( Maxflow (Min+ \Delta )-cut Theorem ) . Let G=(V,E) be a directed weighted graph with a designated source vertex s and a designated sink vertex t . Let f be any maximum (s,t) -flow in G and G^{f} be the corresponding residual graph. Let C be an (s,t) -cut in G . The capacity of C in G is (\lambda+\Delta) if and only if the capacity of C in G^{f} is \Delta , where \Delta\geq 0 . Proof. Let E_{out}(A,H) (likewise E_{in}(A,H) ) denote the set of outgoing edges (likewise the set of incoming edges) of a cut A in a graph H . For any edge e in G , let r(e) be the residual capacity, that is, r(e)=w(e)-f(e) . For any edge e in graph G^{f} , let w^{\prime}(e) denote the capacity of edge e . By construction of G^{f} , for each edge e=(u,v)\in E_{out}(C,G) with r(e)\neq 0 , there exists a forward edge (u,v)\in E_{out}(C,G^{f}) with w^{\prime}(u,v)=r(e) . Similarly, for each edge e=(u,v)\in E_{in}(C,G) with f(e)\neq 0 , there exists a backward edge (v,u)\in E_{out}(C,G^{f}) with w^{\prime}(v,u)=f(e) . This provides us with the following equality. \displaystyle\begin{split}\sum_{e^{\prime}\in E_{out}(C,G^{f})}w^{\prime}(e^{\prime})&=\sum_{e\in E_{out}(C,G)}r(e)+\sum_{e\in E_{in}(C,G)}f(e)\\ &=\sum_{e\in E_{out}(C,G)}(w(e)-f(e))+\sum_{e\in E_{in}(C,G)}f(e)\\ &=\sum_{e\in E_{out}(C,G)}w(e)-\sum_{e\in E_{out}(C,G)}f(e)+\sum_{e\in E_{in}(C,G)}f(e)\\ &=c(C)-(f_{out}(C)-f_{in}(C))\\ &=c(C)-\lambda\quad\quad\text{ Using Lemma \ref{lem : flow conservation}}\end{split} (4) Equation 4 completes the proof. ∎ Appendix C Limitation of the Existing Algorithm for Second (s,t)-mincut We state here a limitation of the existing algorithm given by Vazirani and Yannakakis [ VY92 ] to compute a second (s,t) -mincut. The algorithm for computing an (s,t) -cut of k^{th} minimum capacity by [ VY92 ] uses {\mathcal{O}}(n^{2(k-1)}) maximum (s,t) -flows. So, for k=2 , the algorithm uses {\mathcal{O}}(n^{2}) maximum (s,t) -flow computations. In the same article [ VY92 ] , they stated the following property. Lemma 6 (Lemma 3.2(1) in [ VY92 ] ) . Let G^{f} be the residual graph corresponding to a maximum (s,t) -flow f in G . Let H be an SCC in G^{f} and u,v be a pair of vertices in H . If the capacity of the least capacity cut separating \{u\} and \{v\} is k in H , then the least capacity cut separating \{s,u\} and \{v,t\} has capacity \lambda+k in G . Figure 3 : A counter example for Lemma 3.2(1) in [ VY92 ] (i) A graph G . V\setminus\{t\} is the (s,t) -mincut in G with capacity 1 and c(A) =22. (ii) H is an SCC in G^{f} and c(B,H)=2 Vazirani and Yannakakis [ VY92 ] used Lemma 6 to design an algorithm that computes second (s,t) -mincut using {\mathcal{O}}(n) maximum (s,t) -flow computations (the algorithm preceding Theorem 3.3 in [ VY92 ] ). Unfortunately, Lemma 6 (or Lemma 3.2(1) in [ VY92 ] ) is not correct as shown in Figure 3 (ii) . H is the SCC in G^{f} containing vertices u and v . The least capacity cut B separating \{u\} and \{v\} has capacity 2 in H . By Lemma 6 , the least capacity cut separating \{s,u\} and \{v,t\} must have capacity 2+1=3 in G . However, as it can be verified easily using Figure 3 (i) , A is a least capacity cut separating \{s,u\} and \{v,t\} in G and its capacity is 22 . Therefore, the algorithm stated above Theorem 3.3 in [ VY92 ] , fails to correctly output a second (s,t) -mincut. Appendix D Efficient Algorithms for Computing Second (s,t)-mincut We design two algorithms for computing a second (s,t) -mincut. Our first algorithm uses {\mathcal{O}}(n) maximum (s,t) -flow computations. It is based on the covering technique given in [ BBP23 ] . As our main result of this section, we design our second algorithm that uses \tilde{\mathcal{O}}(\sqrt{n}) maximum (s,t) -flow computations. It is based on a relationship between (s,t) -mincuts and global mincuts as follows. We begin by exploring the relationship between (s,t) -mincuts in G and global mincuts in G^{f} . Let C be any (s,t) -mincut in G . It follows from Lemma 5 that the capacity of C is zero in G^{f} . Hence, every (s,t) -mincut in G is a global mincut in G^{f} . Conversely, again by Lemma 5 , every global mincut C^{\prime} in G^{f} with s\in C^{\prime} and t\in\overline{C^{\prime}} is also an (s,t) -mincut in G . Therefore, there exists a bijective mapping from the set of all (s,t) -mincuts in G to a set of global mincuts in G^{f} . Let us now focus on the set of second (s,t) -mincuts in G . A second (s,t) -mincut in G , by definition, has capacity strictly greater than \lambda . So we need to explore the relationship between the set of (s,t) -cuts in G having capacity greater than \lambda and the set of global cuts in G^{f} of capacity greater than 0. Any (s,t) -cut in G of capacity \lambda+\Delta , \Delta>0 , appears as an (s,t) -cut in G^{f} of capacity \Delta (refer to Theorem 10 ). Therefore, a second (s,t) -mincut in G appears as a second (s,t) -mincut in G^{f} . Now, for global cuts of capacity greater than 0 in G_{f} , we crucially use the insight from the following lemma. Lemma 7 . Let H be a directed weighted graph. H is a strongly connected component (SCC) if and only if the capacity of global mincut in H is strictly greater than zero. Proof. Suppose H is an SCC. Let C be a global mincut in H . Since H is an SCC, for any u\in C and v\in\overline{C} , v is reachable from u . Therefore, there exists an edge e on the path from u to v , that contributes to cut C . Hence, c(C,H)>0 . Suppose the capacity of global mincut is strictly greater than zero in H . Assume to the contrary, H is not an SCC. So, there exists a pair of vertices u,v such that u is not reachable from v or vice-versa. Without loss of generality, assume v is not reachable from u . Let U be the set of vertices reachable from u in H . Since v\notin U , U defines a cut in H . It follows from the selection of vertices in U that c(U,H)=0 , a contradiction. ∎ It follows from Lemma 7 that each cut in G_{f} that subdivides an SCC of G_{f} has capacity greater than 0. There may exist multiple SCCs in the residual graph G^{f} . Therefore, observe that there may also exist global cuts in G^{f} having capacity strictly greater than zero that do not subdivide any SCC. However, if graph G has only two (s,t) -mincuts \{s\} and V\setminus\{t\} , there is only one SCC H=V\backslash\{s,t\} in G^{f} containing at least two vertices and not containing s or t . Observe that, by Lemma 7 , any global cut C with s\in C and t\in\overline{C} in G^{f} has capacity strictly greater than zero if and only if C separates at least one pair of vertices in H . Therefore, we first work with a graph that has at most two (s,t) -mincuts. Finally, exploiting the results for this special case and the structure of {\mathcal{D}}_{PQ}(G) , we extend our results to any general graphs. D.1 Graphs with exactly two (s,t)-mincuts Suppose graph G has exactly two (s,t) -mincuts – \{s\} and V\setminus\{t\} . We now present two algorithms for computing a second (s,t) -mincut in G . Algorithm Using {\mathcal{O}}(n) Maximum (s,t) -flow Computations The following algorithm is immediate for computing a second (s,t) -mincut if graph G has exactly one (s,t) -mincut instead of two. Suppose the (s,t) -mincut in G is V\setminus\{t\} ; otherwise, for the case with only (s,t) -mincut \{s\} , consider the transpose graph of G after swapping the roles of s and t . For every vertex x\in V\setminus\{s,t\} , compute an (s,t) -mincut using one maximum (s,t) -flow in the graph obtained from G by adding an edge (x,t) of infinite capacity. Then, report the (s,t) -mincut of the least capacity among all of the computed (s,t) -mincuts. To use this algorithm in graphs with exactly two (s,t) -mincut, observe that trivially we need {\mathcal{O}}(n^{2}) maximum (s,t) -flow computations. We now extend this algorithm to compute a second (s,t) -mincut using {\mathcal{O}}(n) maximum (s,t) -flow computations for graph G with the two (s,t) -mincuts. Let u be any vertex other than s and t in G . Observe that, for any second (s,t) -mincut C , either u\in C or u\in\overline{C} . Exploiting this observation, we construct two graphs, G^{I} and G^{U} , from G as follows. Graph G^{I} (likewise G^{U} ) is obtained by adding an edge (s,u) (likewise (u,t) ) of infinite capacity. Observe that G^{I} (likewise G^{U} ) has only (s,t) -mincut V\setminus\{t\} (likewise \{s\} ). It follows from the construction of these two graphs that second (s,t) -mincut C appears either in G^{I} or G^{U} . Hence, we can separately compute a second (s,t) -mincut using the algorithm mentioned above in the two graphs and report the minimum between them. This leads to the following result. Lemma 8 . Suppose graph G has exactly two (s,t) -mincuts – \{s\} and V\setminus\{t\} . There is an algorithm that can compute a second (s,t) -mincut in G using {\mathcal{O}}(n) maximum (s,t) -flow computations. Remark 5 . The design of the algorithm stated in Lemma 8 is based on the covering technique of [ BBP23 ] (refer to Theorem 3.2 in Section 3 of [ BBP23 ] ). Algorithm Using One Global Mincut Computation To further improve the running time, we take an approach that (1) exploits the residual graph G^{f} instead of the actual graph G and (2) explores the relation between global mincut and second (s,t) -mincut in G^{f} . As discussed before Appendix D.1 , there is exactly one SCC H in the residual graph G^{f} containing at least two vertices, that is, V\setminus\{s,t\} . Note that any global cut C in H may have a capacity strictly less than the capacity of C in G^{f} . This is because of the existence of edges that are incident on s or t (refer to Figure 4 (i) and (ii) ). Interestingly, we establish the following bijective mapping between the set of all second (s,t) -mincuts in G^{f} and the set of all global mincuts in H . Figure 4 : (i) Global cut A in H (ii) Edge (v,s) contributes to A in G^{f} but not in H (iii) A is a global mincut in H and \{s\}\cup A is a second (s,t) -mincut in G^{f} Lemma 9 . Let C_{1} be a global mincut in H and C_{2} be a second (s,t) -mincut in G^{f} . Then, 1. c(C_{2},G^{f})=c(C_{1},H) , 2. C_{1}\cup\{s\} is a second (s,t) -mincut in G^{f} and C_{2}\setminus\{s\} is a global mincut in H . Proof. Let us consider global mincut C_{1} in graph H , and let c(C_{1},H)=\lambda_{1} . By Lemma 7 , \lambda_{1}>0 . It follows from the construction of G^{f} that C_{1}\cup\{s\} is an (s,t) -cut in G^{f} . Observe that the edge-set of C_{1}\cup\{s\} in G^{f} and the edge-set of C_{1} in H differ only on the set of edges, say E^{\prime} , that are incident on s and t in G^{f} . Since f is maximum (s,t) -flow, by Lemma 5 , s has outdegree zero; likewise, t has indegree zero in G^{f} (refer to Figure 4 ( iii )). So, every edge in E^{\prime} is an incoming edge to (s,t) -cut C_{1}\cup\{s\} in G^{f} . This implies that the contributing edges of (s,t) -cut C_{1}\cup\{s\} in G^{f} are the same as the contributing edges of cut C_{1} in H . Hence, we arrive at the following equation. c(C_{1}\cup\{s\},G^{f})=c(C_{1},H)=\lambda_{1} (5) It is given that C_{2} is a second (s,t) -mincut in G^{f} . Let c(C_{2},G^{f})=\lambda_{2} , where \lambda_{2}>0 . It follows from Lemma 5 that \{s\} and V\setminus\{t\} are the only (s,t) -mincuts in G^{f} . So, any (s,t) -cut in G^{f} except \{s\} and V\setminus\{t\} has capacity at least \lambda_{2} . Since C_{1} is a cut in H , C_{1}\cup\{s\} is neither \{s\} nor V\setminus\{t\} . Moreover, since C_{1}\cup\{s\} is an (s,t) -cut in G^{f} , we get c(C_{2},G^{f})\leq c(C_{1}\cup\{s\},G^{f}) . So, it follows from Equation 5 that c(C_{2},G^{f})\leq\lambda_{1} . Therefore, we arrive at the following inequality. \lambda_{2}\leq\lambda_{1} (6) Observe that second (s,t) -mincut C_{2} must separate a pair of vertices in H since \{s\} and V\setminus\{t\} are (s,t) -mincuts in G^{f} . Thus, the cut C_{2}\setminus\{s\} appears as a global cut in graph H . Thus, we can arrive at the following equation using similar arguments as in the case of Equation 5 . c(C_{2}\setminus\{s\},H)=c(C_{2},G^{f})=\lambda_{2} (7) Since C_{1} is a global mincut in H and C_{2}\setminus\{s\} is a global cut in H , c(C_{1},H)\leq c(C_{2}\setminus\{s\},H) . Therefore, by Equation 7 , we get the following inequality. \lambda_{1}\leq\lambda_{2} (8) It follows from Equations 6 and 8 that \lambda_{2}=\lambda_{1} . Evidently, c(C_{2},G^{f})=c(C_{1},H) and it completes the proof of (1). Now, by Equation 5 , c(C_{1}\cup\{s\},G^{f})=\lambda_{2} and by Equation 7 , c(C_{2}\setminus\{s\},H)=\lambda_{1} . Therefore, (s,t) -cut C_{1}\cup\{s\} is a second (s,t) -mincut in G^{f} and C_{2}\setminus\{s\} is a global mincut in H . This completes the proof of (2). ∎ The following lemma is immediate from Lemma 9 and Theorem 10 . Lemma 10 . Suppose G has exactly two (s,t) -mincuts – \{s\} and V\setminus\{t\} . There is an algorithm that, given any maximum (s,t) -flow in G , can compute a second (s,t) -mincut in G using one global mincut computation. D.2 Graphs with exactly one (s,t)-mincut Suppose G has exactly one (s,t) -mincut V\setminus\{t\} . Let the capacity of (s,t) -mincut in G be \lambda . We now design an algorithm that computes a second (s,t) -mincut in graph G . The results can be extended similarly for the case when the only (s,t) -mincut in G is \{s\} . Let H denote the graph obtained from G^{f} by removing t and the edges incident on t . Observe that the algorithm stated in Lemma 8 actually reduces the problem of computing a second (s,t) -mincut in a graph with two (s,t) -mincuts to a graph that has exactly one (s,t) -mincut. Hence, this algorithm works even for graph G that has exactly one (s,t) -mincut. However, the approach taken for the algorithm stated in Lemma 10 for computing a second (s,t) -mincut in graphs with exactly two (s,t) -mincuts cannot be applied to graph G , which has exactly one (s,t) -mincut. This is because of the following reasons. Lemma 9 crucially exploits the fact that the outdegree of s , as well as the indegree of t , is zero in the corresponding residual graph. However, for graph G , it follows from Theorem 10 that s has outdegree at least 1 in G^{f} . In addition, it is not always necessary that H is an SCC. It shows that there may exist global mincuts C_{1} in H satisfying s\in\overline{C_{1}} and c(C_{1}\cup\{s\},G^{f})\neq c(C_{1},H) . As a result, Equation 5 fails to hold for graph G . Therefore, unlike Lemma 9 , it does not seem possible to establish any bijective mapping between the set of all second (s,t) -mincuts in G^{f} and the set of all global mincuts in H . To overcome these challenges, we construct a new graph H_{s} just by providing a simple modification to graph H as follows. Construction of H_{s} : Graph H_{s} is obtained by adding an edge of infinite capacity from each vertex v to source s in graph H . The following fact follows immediately from the construction of H_{s} . Fact 1 . For any pair of cuts C,C^{\prime} in H_{s} such that s\in C and s\in\overline{C^{\prime}} , c(C,H_{s})\lambda+\lambda^{\prime} since \lambda^{\prime}>\lambda , a contradiction. ∎ It follows from Lemma 14 that the set of all second (s,t) -mincuts of G can be partitioned into disjoint subsets as follows. A pair of cuts C,C^{\prime} belong to different subsets if and only if C and C^{\prime} subdivide different nodes in {\mathcal{D}}_{PQ}(G) . This partitioning allows us to work separately with each node \mu in \mathcal{D}_{PQ}(G) . We now construct a small graph G_{\mu} for node \mu from graph G^{f} by crucially exploiting the topological ordering of DAG \mathcal{D}_{PQ}(G) . Construction of G_{\mu} : Let \tau be a topological ordering of nodes in \mathcal{D}_{PQ}(G) that begins with {\mathbb{T}} and ends with {\mathbb{S}} . Graph G_{\mu} is obtained by modifying graph G^{f} as follows. The set of vertices mapped to the nodes that precede \mu in \tau is contracted into a sink vertex t^{\prime} . Similarly, the set of vertices mapped to the nodes that succeed \mu in \tau is contracted into source vertex s^{\prime} . If \mu=\mathbb{S} (likewise \mathbb{T} ), then we map exactly s to s^{\prime} (likewise t to t^{\prime} ). It follows from the construction of G_{\mu} that s is mapped to s^{\prime} and t is mapped to t^{\prime} in G_{\mu} . Henceforth, without causing ambiguity, we denote an (s^{\prime},t^{\prime}) -cut in G_{\mu} by an (s,t) -cut. Let S and T be the set of vertices in V mapped to s^{\prime} and t^{\prime} respectively. The following lemma is immediate from the construction of graph G_{\mu} and Theorem 7 . Lemma 15 . In graph G_{\mu} , the capacity of (s,t) -mincut is zero and there are at most two (s,t) -mincuts, namely, \{s^{\prime}\} and \{s^{\prime}\}\cup V(\mu) . The following lemma immediately follows from Lemma 15 , Lemma 10 , and Lemma 13 . Lemma 16 . There is an algorithm that can compute a second (s,t) -mincut in G_{\mu} using one global mincut computation in G_{\mu} . Now, given a second (s,t) -mincut in G_{\mu} , we aim to efficiently report a second (s,t) -mincut in graph G . To achieve this goal, in the following lemma, we establish an equivalence between second (s,t) -mincuts in G_{\mu} and (s,t) -cuts of the least capacity in G^{f} that subdivides \mu . Lemma 17 . Let \mu be a node in \mathcal{D}_{PQ}(G) . Let C_{1} be an (s,t) -cut of the least capacity in G^{f} that subdivides \mu into A_{1} and V(\mu)\setminus A_{1} and let C_{2}=\{s^{\prime}\}\cup A_{2} be a second (s,t) -mincut in G_{\mu} , where A_{1},A_{2}\subset V(\mu) . Then, 1. c(C_{1},G^{f})=c(C_{2},G_{\mu}) and 2. \{s^{\prime}\}\cup A_{1} is a second (s,t) -mincut in G_{\mu} and S\cup A_{2} is an (s,t) -cut of the least capacity in G^{f} that subdivides \mu . Proof. Suppose \mu\neq\mathbb{S} or \mathbb{T} . Let c(C_{1},G^{f})=\lambda_{1} and c(C_{2},G_{\mu})=\lambda_{2} . Observe that C_{1} can subdivide set S , T , or both. Let us consider the case when C_{1} subdivides only S . Any prefix of a topological ordering of the nodes in \mathcal{D}_{PQ}(G) defines a 1 -transversal cut in \mathcal{D}_{PQ}(G) . By Theorem 7 and Lemma 5 , S and S\cup V(\mu) are (s,t) -mincuts in G^{f} . Since C_{1}\cap S is an (s,t) -cut in G^{f} , c(C_{1}\cap S,G^{f})\geq c(S,G^{f}) . Again C_{1}\cup S is an (s,t) -cut that subdivides V(\mu) in G^{f} . So, c(C_{1}\cup S,G^{f})\geq\lambda_{1} . By using sub-modularity of cuts (Lemma 2 ) on (s,t) -cuts C_{1} and S in G^{f} , c(C_{1}\cup S,G^{f})=c(C_{1},G^{f}) . Since C_{1} does not divide T , C_{1}\cup S=S\cup A_{1} . Now, by construction of G_{\mu} , S\cup A_{1} appears as the (s,t) -cut \{s^{\prime}\}\cup A_{1} in G_{\mu} such that c(\{s^{\prime}\}\cup A_{1},G_{\mu})=c(S\cup A_{1},G^{f})=\lambda_{1} . By Lemma 15 , \{s^{\prime}\}\cup A_{1} is not an (s,t) -mincut in G_{\mu} since \emptyset\neq A_{1}\subset V(\mu) . Hence, we arrive at the following inequality. \lambda_{1}\geq\lambda_{2} (9) Suppose C_{1} subdivides only T . In this case, using (s,t) -mincut V\setminus T , we can establish \lambda_{1}\geq\lambda_{2} along a similar line to the proof of the case when C_{1} subdivides only S . Suppose C_{1} subdivides both S and T . It follows from the proof of Equation 9 (for the case when C_{1} subdivides only S ) that C_{1}\cup S subdivides only T . Hence, this case reduces to the case when C_{1} subdivides only T . Now, consider the (s,t) -cut C_{2}=\{s^{\prime}\}\cup A_{2} in G_{\mu} . By construction of G_{\mu} , C_{2} appears as the (s,t) -cut S\cup A_{2} in G^{f} such that c(S\cup A_{2},G_{f})=c(C_{2},G_{\mu})=\lambda_{2} . Since, \emptyset\neq A_{2}\subset V(\mu) , S\cup A_{2} is an (s,t) -cut that subdivides \mu in G^{f} . Hence, c(S\cup A_{2},G^{f})\geq\lambda_{1} and we arrive at the following inequality. \lambda_{2}\geq\lambda_{1} (10) It follows from Equations 9 and 10 that \lambda_{1}=\lambda_{2} . This completes the proof. ∎ Remark 6 . Baswana, Bhanja, and Pandey [ BBP23 ] established the result stated in Lemma 17 only for the special case when the least capacity (s,t) -cut C that subdivides node \mu is a (\lambda+1) (s,t) -cut (refer to Lemma 5.10 in [ BBP23 ] ). Hence, Lemma 17 can be seen as an extension of Lemma 5.10 in [ BBP23 ] . By crucially exploiting Lemma 17 and the algorithm designed for computing a second (s,t) -mincut in graph G_{\mu} (Lemma 16 ), we now state our algorithm for computing a second (s,t) -mincut in graph G . The pseudocode of the algorithm is given in Algorithm 1 . Algorithm: The algorithm begins by computing a topological ordering \tau of the nodes of DAG {\mathcal{D}}_{PQ}(G) using one maximum (s,t) -flow computation in G . For each node \mu\neq\mathbb{S},\mathbb{T} in {\mathcal{D}}_{PQ}(G) , compute a global mincut in the SCC H corresponding to node \mu ; otherwise compute a global mincut in the graph H_{s} as stated in Lemma 12 . Let \mu be a node in {\mathcal{D}}_{PQ}(G) such that the global mincut C computed for \mu has the least capacity among all global mincuts computed for other nodes in {\mathcal{D}}_{PQ}(G) . Let S be the set of vertices mapped to nodes in {\mathcal{D}}_{PQ}(G) that precedes node \mu in \tau . It follows from Lemma 16 and the construction of G_{\mu} that S\cup C is a second (s,t) -mincut in G_{\mu} . Therefore, using Lemma 17 and Theorem 10 , the algorithm reports S\cup C as a second (s,t) -mincut in G that has capacity \lambda+c(C,G_{\mu}) . Algorithm 1 Computing Second (s,t) -mincut in G 1: procedure Second Mincut( G,f ) 2: d\leftarrow\sum_{e\in E}w(e) , \lambda_{min}\leftarrow d , C\leftarrow\emptyset,p\leftarrow 0 ; 3: Let \tau be the topological ordering of nodes in \mathcal{D}_{PQ}(G) ; 4: for each node \mu in \mathcal{D}_{PQ}(G) do 5: Let H be the SCC corresponding to node \mu ; 6: if s\in V(\mu) then 7: G^{\prime}\leftarrow Add edge (v,s) to H with w^{\prime}(v,s)=d , for each vertex v\in V(\mu)\setminus\{s\} ; 8: else if t\in V(\mu) then 9: G^{\prime}\leftarrow Add edge (t,v) to H with w^{\prime}(t,v)=d , for each vertex v\in V(\mu)\setminus\{t\} ; 10: else 11: G^{\prime}\leftarrow H ; 12: end if 13: C^{\prime}\leftarrow Compute a global mincut in G^{\prime} ; 14: if \lambda_{min}>c(C^{\prime},G^{\prime}) then 15: Assign \lambda_{min}\leftarrow c(C^{\prime},G^{\prime}) and C\leftarrow C^{\prime} ; 16: p\leftarrow\tau(\mu) ; 17: end if 18: end for 19: Let S be the set of vertices mapped to the suffix of node \mu=\tau(p) in topological ordering \tau 20: if s\in V(\mu) then return (C,\lambda+\lambda_{min}) ; else return (C\cup S,\lambda+\lambda_{min}) ; 21: end procedure We now analyze the running time of our algorithm stated in Algorithm 1 . Running Time: Given a maximum (s,t) -flow in G , we can compute \mathcal{D}_{PQ}(G) and its topological ordering \tau in \mathcal{O}(m) time. Let GM(n^{\prime},m^{\prime}) denote the time taken to compute a global mincut in a directed weighted graph with n^{\prime} vertices and m^{\prime} edges. Observe that GM(n^{\prime},m^{\prime})=\Omega(m^{\prime}) and the SCCs corresponding to the nodes of \mathcal{D}_{PQ}(G) are disjoint from each other. Therefore, it is easy to establish that the overall time taken to compute one global mincut in the SCC corresponding to each node in {\mathcal{D}}_{PQ}(G) is \mathcal{O}(GM(n,m)) . This completes the proof of Theorem 2 (1). Along similar lines to Algorithm 1 , using the algorithm stated in Lemma 8 , it is possible to establish the following result. There is an algorithm that can compute a second (s,t) -mincut in general directed weighted graphs using {\mathcal{O}}(n) maximum (s,t) -flow computations. We now establish the following result that completes the proof of Theorem 2 (2). Lemma 18 . For any directed weighted graph G , there is an algorithm that can compute a global mincut in G using one second (s,t) -mincut computation. Proof. Given graph G , we add two dummy vertices s_{1} and t_{1} to obtain graph G_{1} . Observe that the capacity of (s_{1},t_{1}) -mincut in G_{1} is zero. Based on the capacity of global mincut in G , the proof can be divided into two cases: (1) the capacity of global mincut in G is zero, and (2) it is strictly greater than zero. For Case 1 , we can compute a global mincut in G by taking the following approach. Any global mincut C in G appears as an (s_{1},t_{1}) -mincut s_{1}\cup C in G_{1} . So, G_{1} has at least three (s_{1},t_{1}) -mincuts. It follows that there are at least four nodes in \mathcal{D}_{PQ}(G_{1}) . Let \tau be a topological ordering of nodes in \mathcal{D}_{PQ}(G_{1}) and let C be the set of vertices mapped to the suffix of \tau containing two nodes. Since c(\{s\},G_{1})=0 , report C\setminus\{s\} as the global mincut in G . For Case 2 , G_{1} has exactly two (s_{1},t_{1}) -mincuts: \{s_{1}\} and \{s_{1}\}\cup V . So, any second (s_{1},t_{1}) -mincut in G_{1} must subdivide V . Suppose the algorithm for computing second (s_{1},t_{1}) -mincut in G_{1} returns (s_{1},t_{1}) -cut C . By Lemma 9 (2) , we can report C\setminus\{s_{1}\} as a global mincut in G . ∎ The best-known algorithm for computing a global mincut in directed graphs is given by Cen et al. [ CLN+21 ] as follows. Theorem 11 (Theorem I.1 in [ CLN+21 ] ) . Let G be a directed graph on n vertices with integer edge capacities. There exists an algorithm that computes a global mincut in G using \tilde{\mathcal{O}}(\sqrt{n}) maximum (s,t) -flow computations with high probability. Algorithm 1 uses \mathcal{O}(n) invocations of the algorithm in Theorem 11 . By using union bound, it is easy to show that Algorithm 1 computes a second (s,t) -mincut in G with high probability. Theorem 11 and Theorem 2 (1) lead to Theorem 1 . Appendix E Compact Structure for All (\lambda+1) (s,t)-cuts In this section, we present a compact structure for storing and characterizing all (\lambda+1) (s,t) -cuts for undirected multi-graphs. So, let us consider G to be an undirected multi-graph for this section. The construction of our structure involves the following two steps. In the first step, we design an {\mathcal{O}}(m) space structure consisting of one DAG and a special set of edges. In the final step, we improve the space occupied by this structure to {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) . Unlike the existing approaches [ BBP23 ] , to arrive at our structure, we take a flow-based approach that crucially exploits the characterization of (\lambda+1) (s,t) -cuts using a maximum (s,t) -flow (stated in Theorem 9 ). E.1 An {\mathcal{O}}(m) space Structure To design a compact structure for storing and characterizing all (\lambda+1) (s,t) -cuts of G , our aim is to transform all the (\lambda+1) (s,t) -cuts into (s,t) -mincuts. In particular, we want to remove a set of edges E^{\prime} from G such that every (\lambda+1) (s,t) -cut of G becomes an (s,t) -mincut in the resulting graph. Let f be any given maximum (s,t) -flow in G . Observe that by Theorem 8 (Maxflow-Mincut Theorem), the removal of a set of edges carrying zero flow in f does not reduce the capacity of (s,t) -mincut. Let NoFlow denote the set of all edges that carry zero flow in f . It is evident that every (s,t) -cut has capacity at least \lambda in G\setminus\textsc{NoFlow} . However, is it guaranteed that every (\lambda+1) (s,t) -cut is an (s,t) -mincut in G\setminus\textsc{NoFlow} ? To address this question, we now introduce the concept of anchor edges. Definition 4 (Anchor edge) . For any given maximum (s,t) -flow f , an edge e is said to be an anchor edge if e contributes to a (\lambda+1) (s,t) -cut and f(e)=0 . The following property immediately follows from Definition 4 and Theorem 9 for the set of anchor edges. Lemma 19 . Given any maximum (s,t) -flow in G , for every (\lambda+1) (s,t) -cut C , there is exactly one anchor edge that contributes to C . By using Lemma 19 , it is a simple exercise to show that the set of anchor edges, denoted by {\mathcal{A}} , is unique for maximum (s,t) -flow f . This helps in establishing the following crucial property that holds even for any superset E^{\prime} of anchor edges carrying zero flow in G . Lemma 20 . Let E^{\prime}\subseteq E be a set of edges in G such that \mathcal{A}\subseteq E^{\prime}\subseteq\textsc{NoFlow} . In G\setminus E^{\prime} , the following properties hold. 1. The capacity of (s,t) -mincut is \lambda in G\setminus E^{\prime} . 2. Every (\lambda+1) (s,t) -cut as well as (s,t) -mincut in G , is an (s,t) -mincut in G\setminus E^{\prime} . Proof. Since E^{\prime}\subseteq\textsc{NoFlow} , removal of all the edges from E^{\prime} does not decrease the value of maximum (s,t) -flow. Therefore, by Maxflow-Mincut Theorem, the capacity of (s,t) -mincut in G\setminus E^{\prime} is \lambda . It follows that every (s,t) -mincut in G remains an (s,t) -mincut in G\setminus E^{\prime} . Since \mathcal{A}\subseteq E^{\prime} , Lemma 19 implies that for every (\lambda+1) (s,t) -cut C in G , exactly one anchor edge is removed from the edge-set of C . So, the capacity of every (\lambda+1) (s,t) -cut in G is reduced by at least one in G\setminus E^{\prime} . Moreover, it follows from Theorem 9 that there is exactly one edge in E(C) carrying no flow. Since E^{\prime}\subseteq\textsc{NoFlow} , the capacity of every (\lambda+1) (s,t) -cut in G is reduced by exactly 1 in G\setminus E^{\prime} . Therefore, every (\lambda+1) (s,t) in G is an (s,t) -mincut in G\setminus E^{\prime} . ∎ Let \mathcal{S}(H) be any compact structure for storing and characterizing all the (s,t) -mincuts in any graph H using a property, say \mathcal{P} . It follows from Lemma 20 that every (\lambda+1) (s,t) -cut in G satisfies property \mathcal{P} in \mathcal{S}(G\setminus E^{\prime}) . However, by Lemma 20 (2) , every (s,t) -mincut in G also satisfies property \mathcal{P} . Moreover, there may exist many (s,t) -cuts other than the (\lambda+1) (s,t) -cuts and (s,t) -mincuts in G that have also become (s,t) -mincuts in G\setminus E^{\prime} . This is because a (\lambda+k) (s,t) -cut may contain exactly k anchor edges (refer to Figure 5 (i) for k=2 ). However, we show using Theorem 9 and Lemma 19 that E^{\prime} is sufficient to characterize (\lambda+1) (s,t) -cuts using {\mathcal{S}}(G\setminus E^{\prime}) as follows. Figure 5 : A blue (likewise green) edge represents that the edge is carrying nonzero flow (likewise an anchor edge). (i) C is a (\lambda+2) (s,t) -cut and it contains two anchor edges. ( ii ) Graph satisfying |\textsc{NoFlow}|=\Omega(n^{2}) with exactly one anchor edge. ( iii ) Graph with exactly (n-2) anchor edges. Lemma 21 . Let E^{\prime}\subseteq E be a set of edges in G such that \mathcal{A}\subseteq E^{\prime}\subseteq\textsc{NoFlow} . There is a structure \mathcal{S}(G\setminus E^{\prime}) that stores and characterizes all (\lambda+1) (s,t) -cuts and (s,t) -mincuts in G using property {\mathcal{P}} and set of edges E^{\prime} as follows. 1. An (s,t) -cut C is an (s,t) -mincut in G if and only if C satisfies \mathcal{P} in \mathcal{S}(G\setminus{E^{\prime}}) and no edge in {E^{\prime}} contributes to C . 2. An (s,t) -cut C is a (\lambda+1) (s,t) -cut in G if and only if C satisfies \mathcal{P} in {\mathcal{S}}(G\setminus{E^{\prime}}) and exactly one edge of {E^{\prime}} contributes to C . Proof. Let C be an (s,t) -mincut and C^{\prime} be a (\lambda+1) (s,t) -cut in G . By Lemma 20 , both C and C^{\prime} are (s,t) -mincuts in graph G\setminus E^{\prime} . Hence, both C and C^{\prime} , satisfy property \mathcal{P} in \mathcal{S}(G\setminus{E^{\prime}}) . Since G is undirected, by Theorem 8 (Maxflow-Mincut Theorem), there is no edge from NoFlow , and hence from E^{\prime} , that contributes to (s,t) -mincut C in G . For (\lambda+1) (s,t) -cut C^{\prime} , it follows from Theorem 9 that exactly one edge from NoFlow contributes to C^{\prime} , which must be an anchor edge by Lemma 19 . Therefore, exactly one edge from E^{\prime} contributes to C^{\prime} since {\mathcal{A}}\subseteq E^{\prime}\subseteq\textsc{NoFlow} . Let us consider an (s,t) cut C that satisfies property \mathcal{P} in {\mathcal{S}}(G\setminus E^{\prime}) . It follows from from the property of compact structure \mathcal{S} that C has capacity \lambda in G\setminus E^{\prime} . Therefore, if no edge from E^{\prime} contributes to C , then C is an (s,t) -mincut in G . Similarly, if exactly one edge from E^{\prime} is contributing to C , then C has capacity exactly \lambda+1 in G . ∎ The best-known structure for storing and characterizing all (s,t) -mincuts is the DAG {\mathcal{D}}_{PQ} given by Picard and Queyranne [ PQ80 ] (refer to Section 3 ). For undirected multi-graph G\setminus E^{\prime} , using the result of [ GY95 ] , it is easy to show that there is an integer-weighted graph G^{\prime} such that the space occupied by the structure {\mathcal{D}}_{PQ}(G^{\prime}) is {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) and it stores and characterizes all (s,t) -mincuts of G\setminus E^{\prime} (the proof is given in Appendix J for completeness). We stress that if G is a simple graph, then {\mathcal{D}}_{PQ}(G\setminus E^{\prime}) is the same as {\mathcal{D}}_{PQ}(G^{\prime}) . For simplicity of exposition, without causing any ambiguity, we use {\mathcal{D}}_{PQ}(G\setminus E^{\prime}) to denote {\mathcal{D}}_{PQ}(G^{\prime}) . So, we use {\mathcal{D}}_{PQ} as {\mathcal{S}} to obtain our structure {\mathcal{D}}_{PQ}(G\setminus E^{\prime}) . By construction, structure {\mathcal{D}}_{PQ}(G\setminus E^{\prime}) also occupies {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space. However, storing set of edges E^{\prime} can require {\mathcal{O}}(m) space since E^{\prime}\subseteq\textsc{NoFlow} . E.2 Bounding the Cardinality of The Set of Anchor Edges In this section, we provide a tight bound on the cardinality of the set of all anchor edges \mathcal{A} . We present an efficient algorithm that, exploiting the properties of anchor edges, computes a set of edges \mathcal{F} such that the following two properties hold. 1. The set of all anchor edges is a subset of \mathcal{F} . 2. The number of edges belonging to \mathcal{F} is at most n-2 . By Definition 4 , every anchor edge belongs to set NoFlow . However, there exist graphs H such that, for any maximum (s,t) -flow in H , the cardinality of set NoFlow can be \Omega(n^{2}) , yet the number of anchor edges is only \mathcal{O}(1) (refer to Figure 5 ( ii )). So, NoFlow provides a loose upper bound on the number of anchor edges. Naturally, the question arises whether it is possible to eliminate a large number of edges from NoFlow while still keeping the set of all anchor edges intact. We answer this question in the affirmative by exploiting the following lemma. Lemma 22 . Let \mathbb{H} be a cycle formed using a subset of edges in NoFlow . Then, no edge in \mathbb{H} can be an anchor edge. Proof. Consider any edge e\in\mathbb{H} and C be any (s,t) -cut in G such that e\in E(C) . Since C is a cut, C must intersect cycle \mathbb{H} at least twice. Hence, C contains at least two edges that carry no flow. Therefore, it follows from Theorem 9 that C cannot be a (\lambda+1) (s,t) -cut. Hence, by Definition 4 , e cannot be an anchor edge. ∎ We now use Lemma 22 to construct a spanning forest G_{\mathcal{F}} to provide an upper bound on the cardinality of set {\mathcal{A}} . Construction of Spanning Forest G_{\mathcal{F}}=(V,{\mathcal{F}}) : The vertex set of G_{\mathcal{F}} is the same as G . Initially, there is no edge in G_{\mathcal{F}} . We construct graph G_{\mathcal{F}} incrementally by executing the following step for each edge e in NoFlow . If a cycle is formed in G_{\mathcal{F}}\cup\{e\} , then by Lemma 22 , e cannot be an anchor edge. Hence, we ignore edge e . Otherwise, if there is no cycle in G_{\mathcal{F}}\cup\{e\} , then insert edge e to G_{\mathcal{F}} . It follows from the construction of G_{\mathcal{F}} that \mathcal{A}\subseteq\mathcal{F} . Moreover, |\mathcal{F}| is at most n-1 since G_{\mathcal{F}} is a spanning forest. We now show a tight bound on |\mathcal{A}| , as well as |\mathcal{F}| , in the following lemma. Lemma 23 . Set {\mathcal{A}} , as well as set \mathcal{F} , contains at most (n-2) edges. Proof. Let us assume to the contrary that {\mathcal{F}} contains exactly n-1 edges. It follows that G_{\mathcal{F}} is a spanning tree. Hence, {\mathcal{F}} contains at least one edge from the edge-set of every (s,t) -cut in G . It implies that there exists an (s,t) -mincut C in G such that {\mathcal{F}} contains at least one edge from the edge-set of C . By Theorem 8 (Maxflow-Mincut Theorem), for every edge e\in E(C) , f(e)=1 . Thus, {\mathcal{F}} contains an edge e such that f(e)=1 , which is a contradiction since \mathcal{F}\subseteq NoFlow . Since \mathcal{A}\subseteq\mathcal{F} , it follows that the cardinality of \mathcal{A} is at most n-2 . ∎ We show that there also exist graphs where {\mathcal{A}} contains exactly n-2 edges (refer to Figure 5 (iii) ). Therefore, the bound on the set {\mathcal{A}} given in Lemma 23 is tight. It is easy to show using Union-Find data structure [ Tar75 ] that, given any maximum (s,t) -flow, the time taken for computing set {\mathcal{F}} (containing all anchor edges) is {\mathcal{O}}(m\alpha(m,n)) , where \alpha(m,n) denotes the inverse Ackermann function. Interestingly, we show that there is an algorithm that, given maximum (s,t) -flow f , can compute only set \mathcal{A} in \mathcal{O}(m) time (refer to Appendix I ). This completes the proof of the following Theorem. Theorem 12 (Anchor Edges: Cardinality & Computation) . Let G be any undirected multi-graph on n vertices and m edges. For any maximum (s,t) -flow f in G , there is a set containing at most n-2 edges of G , called the anchor edges, such that for any minimum+1 (s,t) -cut C in G , exactly one anchor edge contributes to C . Moreover, given a maximum (s,t) -flow f , there is an algorithm that computes all anchor edges for f in {\mathcal{O}}(m) time. DAG \mathcal{D}_{PQ}(G\setminus E^{\prime}) occupies \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) space (established in Appendix E.1 ). Therefore, Lemma 21 and Theorem 12 complete the proof of Theorem 4 . Appendix F Dual Edge Sensitivity Oracle for (s,t)-mincuts In this section, for simple graphs, we design a dual edge sensitivity oracle for (s,t) -mincut (refer to Definition 1 ) that occupies subquadratic space while achieving a nontrivial query time. Henceforth, let us consider G to be a simple graph. As a warm-up, we first explain the folklore result that the residual graph G^{f} acts as a simple dual edge sensitivity oracle that achieves {\mathcal{O}}(m) query time. Note that G^{f} occupies {\mathcal{O}}(m)={\mathcal{O}}(n^{2}) space in the worst case. In order to break this quadratic barrier for simple graphs, our main result is to show that, the query algorithm used for the residual graph G^{f} can be applied to DAG {\mathcal{D}}_{PQ}(G\setminus{\mathcal{A}}) and set of anchor edges {\mathcal{A}} from Theorem 4 even if {\mathcal{D}}_{PQ}(G\setminus{\mathcal{A}})\cup{\mathcal{A}} is just a quotient graph of G^{f} . For simplicity, we denote {\mathcal{D}}_{PQ}(G\setminus{\mathcal{A}}) by \mathcal{D}(\mathcal{A}) . We now state two properties of {\mathcal{D}}({\mathcal{A}}) that are used crucially in arriving at our results. Observe that, by Lemma 3 , if both endpoints of any edge e are mapped to the same node in {\mathcal{D}}_{PQ}(G) , then the failure of edge e does not reduce the capacity of (s,t) -mincut. This property is exploited crucially to show that DAG {\mathcal{D}}_{PQ}(G) acts as a single edge sensitivity oracle for (s,t) -mincut [ PQ80 ] . Interestingly, {\mathcal{D}}({\mathcal{A}}) extends the above property of {\mathcal{D}}_{PQ}(G) to a pair of edges as follows. If all the endpoints of the pair of failed edges are mapped to the same node in {\mathcal{D}}({\mathcal{A}}) , then the (s,t) -mincut capacity remains unchanged. This property is a consequence of the following lemma, which follows from Theorem 4 . Lemma 24 . Let u and v be any pair of vertices in G . If u and v are mapped to the same node in {\mathcal{D}}({\mathcal{A}}) , then the (s,t) -cut of the least capacity that separates u and v has capacity at least \lambda+2 . Proof. Let u,v be any pair of vertices mapped to the same node in {\mathcal{D}}({\mathcal{A}}) . Suppose there is a (\lambda+1) (s,t) -cut C satisfying u\in C and v\in\overline{C} . It follows that {\mathcal{D}}({\mathcal{A}}) fails to store C . Therefore, existence of such a cut C is not possible due to Theorem 4 . ∎ We now state the following relation between the edges of DAG {\mathcal{D}}({\mathcal{A}}) and maximum (s,t) -flow f in G , which is immediate from anchor edge definition (Definition 4 ), Lemma 48 , and Theorem 4 . Lemma 25 . For any edge e=(x,y) in {\mathcal{D}}({\mathcal{A}}) , the corresponding undirected edge e in G satisfies f(e)=1 and e carries flow in the direction y to x . Moreover, for any edge e\in{\mathcal{A}} , f(e)=0 . We consider only the failure of edges, the insertion case is given in Appendix G for better readability. Suppose the two failed edges are e_{1}=(x_{1},y_{1}) and e_{2}=(x_{2},y_{2}) . The failure of any edge carrying no flow does not affect the capacity of (s,t) -mincut as f remains unchanged. Henceforth, without loss of generality, assume that e_{1} always carries flow in the direction x_{1} to y_{1} . The analysis is along a similar line if e_{1} carries flow in the direction y_{1} to x_{1} . F.1 An {\mathcal{O}}(m) Space Data Structure and {\mathcal{O}}(m) Query Time The failed edge e_{1} has been carrying flow of value 1 . So, we first reduce the value of (s,t) -flow in G by 1 as follows. It follows from the construction of G^{f} that there is at least one (t,s) -path P_{1} in G^{f} satisfying the following. Path P_{1} contains the residual edge (y_{1},x_{1}) for edge e_{1} , and for every edge (v,u) in P_{1} , the corresponding edge (u,v) in G carries flow in the direction u to v . Path P_{1} can be obtained in {\mathcal{O}}(m) time by using any traversal algorithm. In graph G\setminus\{e_{1}\} , we now obtain a new (s,t) -flow f_{1} of value \lambda-1 from f . For this purpose, we define the following operation, which is also used later for our analysis of breaking the quadratic barrier for dual edge sensitivity oracle for (s,t) -mincut in Appendix F.2 . Update_Path (H,P) : Let H be a directed graph and P be any path in H . For every edge e^{\prime\prime}=(p,q) in P , this function Update_Path removes e^{\prime\prime} from H and adds an edge (q,p) in H . We first update G^{f} using Update_Path (G^{f},P_{1}) ; and then, remove from the resulting graph the pair of edges (x_{1},y_{1}) and (y_{1},x_{1}) corresponding to the failed edge e_{1} in G . Let G^{f_{1}} be the obtained graph. Observe that G^{f_{1}} is the residual graph of G\setminus\{e_{1}\} for an (s,t) -flow f_{1} of value \lambda-1 . In G\setminus\{e_{1}\} , we want to determine whether f_{1} is a maximum (s,t) -flow. To determine this, we use the following lemma, which was established by Ford and Fulkerson [ FF56 ] . Lemma 26 ( [ FF56 ] ) . For any graph \mathcal{G} with an (s,t) -flow f^{\prime} , f^{\prime} is a maximum (s,t) -flow if and only if there is no (s,t) -path in the residual graph \mathcal{G}^{f^{\prime}} . It follows from Lemma 26 that in graph G^{f_{1}} , we need to verify whether there is any path P^{\prime} from s to t . Note that at most one (s,t) -path may exist; otherwise, it can be shown that the capacity of (s,t) -mincut in G is strictly greater than \lambda . So, in G\setminus\{e_{1}\} , if P^{\prime} exists, then, by Lemma 26 , the capacity of (s,t) -mincut is \lambda ; otherwise the capacity of (s,t) -mincut is \lambda-1 . We update path P^{\prime} in G^{f_{1}} to obtain a graph G^{f_{2}} by following the construction of residual graph (refer to Section 3 ); otherwise, G^{f_{1}} is the same as G^{f_{2}} if P^{\prime} does not exist. It follows that graph G^{f_{2}} is the residual graph for a maximum (s,t) -flow f_{2} (of value either \lambda-1 or \lambda ) in graph G\setminus\{e_{1}\} . We now want to verify whether the failure of e_{2} reduces the capacity of (s,t) -mincut in G\setminus\{e_{1}\} . Interestingly, the following lemma ensures that DAG {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) is sufficient for this purpose. Lemma 27 ( [ PQ80 ] , [ BP22 ] , and Lemma 4.4 in [ BBP23 ] ) . For any undirected multi-graph {\mathcal{G}} , upon failure of any edge e in {\mathcal{G}} , the capacity of (s,t) -mincut reduces by 1 if and only if both endpoints of e are mapped to different nodes of {\mathcal{D}}_{PQ}({\mathcal{G}}) . Moreover, if (s,t) -mincut reduces, then, for any topological ordering \tau of the nodes of {\mathcal{D}}_{PQ}({\mathcal{G}}) , the suffix of \tau containing exactly one endpoint of e defines an (s,t) -mincut after the failure of edge e . By using the residual graph G^{f_{2}} , we construct {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) in {\mathcal{O}}(m) time by following the construction given in Section 3.1 . It follows from Lemma 27 that we can determine whether e_{2} contributes to an (s,t) -mincut in G\setminus\{e_{1}\} in {\mathcal{O}}(1) time. Suppose e_{2} contributes to an (s,t) -mincut in G\setminus\{e_{1}\} . If the (s,t) -mincut capacity in G\setminus\{e_{1}\} is \lambda-1 (likewise, \lambda ), then after the failure of two edges e_{1},e_{2} , the capacity of (s,t) -mincut in G is \lambda-2 (likewise, \lambda-1 ). In a similar way, we can determine the capacity of (s,t) -mincut in G after the failure of two edges e_{1},e_{2} if e_{2} does not contribute to any (s,t) -mincut in G\setminus\{e_{1}\} . Moreover, again by Lemma 27 , reporting an (s,t) -mincut C in G\setminus\{e_{1}\} after the failure of edge e_{2} requires {\mathcal{O}}(m) time. It is easy to observe that C is also an (s,t) -mincut in G after the failure of two edges e_{1},e_{2} . It leads to the following lemma. Lemma 28 . There is an {\mathcal{O}}(m) space data structure that, after the failure of any given pair of query edges, can report an (s,t) -mincut and its capacity in {\mathcal{O}}(m) time. F.2 Breaking Quadratic Barrier We now show that DAG {\mathcal{D}}({\mathcal{A}}) and set of edges {\mathcal{A}} stated in Theorem 4 act as a dual edge sensitivity oracle for (s,t) -mincut and occupies subquadratic space for simple graphs. It follows from the proof of Lemma 28 that, given residual graph G^{f} , the main objective is to design graph {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . In order to obtain \mathcal{D}_{PQ}(G\setminus\{e_{1}\}) , the residual graph G^{f} plays a crucial role in computing a maximum (s,t) -flow in graph G\setminus\{e_{1}\} . However, the main challenge arises in computing a maximum (s,t) -flow in graph G\setminus\{e_{1}\} using only DAG {\mathcal{D}}({\mathcal{A}}) and set of edges {\mathcal{A}} from Theorem 4 . This is because of the following reason. {\mathcal{D}}({\mathcal{A}}) initially occupies {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space. But, it seems quite possible that after the removal of edge e_{1} , we need the reachability information among the vertices that are mapped to single nodes in {\mathcal{D}}({\mathcal{A}}) . This would blow up the space, as well as time, to arrive at {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) ; and hence, it defeats our objective of designing a subquadratic space dual edge sensitivity oracle. Interestingly, we show, using Lemma 24 and structural properties of {\mathcal{D}}({\mathcal{A}}) , that such event never occurs; and {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} is sufficient to design {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) using {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space and {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) time. An edge e is said to be mapped to a node \mu in {\mathcal{D}}({\mathcal{A}}) if both endpoints of e are mapped to \mu . It follows from Lemma 24 and Lemma 25 that if both failed edges are mapped to nodes of {\mathcal{D}}({\mathcal{A}}) or belong to set {\mathcal{A}} , then the capacity of (s,t) -mincut remains unchanged. Therefore, without loss of generality, we assume that endpoints of edge e_{1} are mapped to different nodes of {\mathcal{D}}({\mathcal{A}}) . Construction of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) using Structure {\mathcal{D}}({\mathcal{A}}) and Edge Set {\mathcal{A}} Let us determine whether failure of e_{1} reduces the capacity of (s,t) -mincut in G . It follows from Lemma 25 that e_{1} must carry flow. So, there exists a (t,s) -path P_{r} in the residual graph containing the edge (y_{1},x_{1}) such that for every edge in P_{r} , the corresponding edge in G is carrying flow. Interestingly, the following lemma ensures that there is also a path P in {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} such that P is a quotient path of P_{r} . Lemma 29 . For any pair of vertices u,v , let \mu and \nu be the nodes to which u and v are mapped in \mathcal{D}(\mathcal{A}) . There exists an (u,v) -path Q_{1} in G^{f} if and only if there exists a (\mu,\nu) -path Q_{2} in {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} . Moreover, Q_{2} is a quotient path of Q_{1} . Proof. The proof of the forward direction is immediate since {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} is a quotient graph of residual graph G^{f} . Let us prove the converse part. Suppose there is an (\mu,\nu) -path in {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} . Since G is undirected, by construction, every node of {\mathcal{D}}({\mathcal{A}}) corresponds to an SCC in G^{f} . Moreover, since {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} is a quotient graph of residual graph G^{f} , there is a path in G^{f} from every vertex that is mapped to \mu to every vertex that is mapped to \nu . ∎ Now, to obtain the (s,t) -mincut capacity in G\setminus\{e_{1}\} , we need to first reduce the value of (s,t) -flow in G by 1 using the path P_{r} . As discussed in Appendix F.1 , this can be achieved by performing Update_Path (G^{f},P_{r}) , and then, removing the pair of edges (x_{1},y_{1}) and (y_{1},x_{1}) from the resulting graph corresponding to the failed edge e_{1} in G . Let f_{1} be the obtained (s,t) -flow in graph G\setminus\{e_{1}\} and let G^{f_{1}} be the corresponding residual graph after this operation. It follows immediately from Lemma 29 that we can achieve the same objective by performing Update_Path ({\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}},P) , and then, removing the pair of edges (x_{1},y_{1}) and (y_{1},x_{1}) from the resulting graph corresponding to the failed edge e_{1} in G . Let D_{1} be the resulting graph from {\mathcal{D}}({\mathcal{A}})\cup{\mathcal{A}} . The following lemma immediately follows from the construction of D_{1} and Lemma 29 ; and it states the relationship between graph D_{1} and G^{f_{1}} . Lemma 30 . Graph D_{1} satisfies the following two properties. 1. D_{1} is a quotient graph of G^{f_{1}} , where f_{1} is the (s,t) -flow in G\setminus\{e_{1}\} after applying operation Update_Path (G^{f},P_{r}) and removal of edges (x_{1},y_{1}) , (y_{1},x_{1}) from the resulting graph. 2. A pair of vertices u,v are mapped to the same node in {\mathcal{D}}({\mathcal{A}}) if and only if u,v are mapped to the same node in D_{1} . We have now graph G\setminus\{e_{1}\} and (s,t) -flow f_{1} of value \lambda-1 . The aim is now to determine using D_{1} whether (s,t) -flow f_{1} is a maximum (s,t) -flow in G\setminus\{e_{1}\} or the value of (s,t) -flow can be increased by 1 . For this purpose, we verify whether an (s,t) -path P^{\prime} exists in D_{1} . Lemma 30 (2) ensures that the existence of path P^{\prime} can be determined in {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) time. Suppose path P^{\prime} exists. By Lemma 30 (1), the capacity of (s,t) -mincut is \lambda in G\setminus\{e_{1}\} . It follows from Lemma 30 (1), and the construction of D_{1} and G^{f_{1}} , that the mapping stated in Lemma 29 remains intact between D_{1} and G^{f_{1}} . Hence, there is an (s,t) -path P_{r}^{\prime} in G^{f_{1}} such that P^{\prime} is a quotient path of P_{r}^{\prime} . Upon updating path P_{r}^{\prime} in G^{f_{1}} by following the construction of residual graph (refer to Section 3 ), let f_{2} be the maximum (s,t) -flow of value \lambda obtained in G\setminus\{e_{1}\} . Let G^{f_{2}} denote the corresponding residual graph. However, by Lemma 30 , we update path P^{\prime} in D_{1} , instead of updating path P_{r}^{\prime} in G^{f_{1}} , by following the construction of residual graph. Let D_{2} be the resulting graph. If P^{\prime} does not exist, then the capacity of (s,t) -mincut is \lambda-1 in G\setminus\{e_{1}\} , D_{1}=D_{2} , f_{1}=f_{2} , and G^{f_{1}}=G^{f_{2}} . Now, the following lemma states the properties of graph D_{2} . Lemma 31 . Graph D_{2} satisfies the following three properties. 1. D_{2} is a quotient graph of G^{f_{2}} , where f_{2} is a maximum (s,t) -flow in G\setminus\{e_{1}\} . 2. A pair of vertices u,v are mapped to the same node in {\mathcal{D}}({\mathcal{A}}) if and only if u,v are mapped to the same node in D_{2} . 3. If a pair of vertices u,v is mapped to the same node in D_{2} then u,v belong to the same SCC in G^{f_{2}} . Proof. The proof of properties (1) and (2) follows directly from the construction of D_{2} and Lemma 30 . We now establish the property (3) of D_{2} . It follows from Lemma 24 that any (s,t) -cut that separates any pair of vertices mapped to the same node in {\mathcal{D}}({\mathcal{A}}) has capacity at least \lambda+2 in G . Removal of edge e_{1} can reduce the capacity of any (s,t) -cut by at most 1 . Therefore, by property (2), the least capacity (s,t) -cut in G\setminus\{e_{1}\} that separates any pair of vertices u,v mapped to the same node in D_{2} has capacity at least \lambda+1 . Moreover, the capacity of (s,t) -mincut in G\setminus\{e_{1}\} is at most \lambda . Since graph G is undirected, by using the proof of Lemma 3 , vertices u,v must belong to the same SCC in G^{f_{2}} . ∎ We now obtain DAG {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) from graph D_{2} . Let \mathbb{D} be the graph obtained by contracting every SCC of D_{2} into a single node. The following lemma establishes a relation between {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) and \mathbb{D} . Lemma 32 . A pair of vertices u,v are mapped to the same node in \mathbb{D} if and only if u,v are mapped to the same node in {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . Proof. Suppose there is a pair of vertices u,v that are mapped to the same node in \mathbb{D} . It follows from the construction of \mathbb{D} that u,v are either mapped to the same node in D_{2} or belong to an SCC in D_{2} . In the former case, by Lemma 31 (3), u,v belong to the same SCC in G^{f_{2}} . We now consider the latter case. It follows from Lemma 31 (1) and (3) that a pair of vertices belonging to an SCC in D_{2} also belongs to the same SCC in G^{f_{2}} . Hence, by construction of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) , u,v are mapped to the same node in {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . Lets us prove the converse part. Suppose u and v are mapped to the same node of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . Since G is undirected, it implies from the construction of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) that u and v belong to the same SCC in the residual graph G^{f_{2}} for maximum (s,t) -flow f_{2} in G\setminus\{e_{1}\} . Therefore, by Lemma 31 (1), u and v either belong to the same node in D_{2} or in an SCC in D_{2} . Hence, by construction of {\mathbb{D}} , u and v are mapped to the same node in \mathbb{D} . ∎ It follows from Lemma 31 (1), Lemma 32 , and the construction of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) that the set of edges of \mathbb{D} is the same as the set of edges of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . Therefore, the following lemma is immediate. Lemma 33 . Graph \mathbb{D} is the DAG {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) . It follows from Lemma 31 (2) that D_{2} occupies {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) space, and hence, the contraction of each SCC in D_{2} takes {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time. Therefore by Lemma 33 , given {\mathcal{D}}({\mathcal{A}}) and set of edges {\mathcal{A}} , there is an algorithm that, using {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) space, can compute graph {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) in {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time. Now, similar to the discussion in Appendix F.1 and Lemma 27 , it is easy to observe that, given {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) , only {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time is required to report an (s,t) -mincut C and its capacity after the failure of edges e_{1},e_{2} in graph G . To report the set of edges contributing to (s,t) -mincut C , we report every edge of {\mathcal{D}}_{PQ}(G\setminus\{e_{1}\}) whose one endpoint is in C and the other is in \overline{C} . This can also be accomplished in the same {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time. This, along with Theorem 14 , completes the proof of the following theorem. Theorem 13 (Dual Edge Sensitivity Oracle for Simple Graphs) . Let G be an undirected simple graph on n vertices and m edges with designated source and sink vertices s and t , respectively. Let \lambda be the capacity of (s,t) -mincut in G . There exists a data structure occupying {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space that can report an (s,t) -mincut in {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) time after the failure or insertion of any pair of given query edges in G . For simple graphs, the capacity of (s,t) -mincut is bounded by n-1 . Therefore, Theorem 13 leads to Theorem 5 . We now analyze the time taken for computing our compact structure stated in Theorem 4 . It follows from Theorem 12 that, given maximum (s,t) -flow f , we can compute set {\mathcal{A}} in {\mathcal{O}}(m) time. Moreover, given {\mathcal{A}} and f , the construction of {\mathcal{D}}({\mathcal{A}}) requires {\mathcal{O}}(m) time. This completes the proof of Theorem 6 . Appendix G Handling Dual Edge Insertions Suppose the two query edges to be inserted into simple graph G are e_{1}=(x_{1},y_{1}) and e_{2}=(x_{2},y_{2}) . For any directed graph H_{d} and an undirected edge e=(a,b) , let H_{d}\cup\{e\} denote the graph obtained from H_{d} after insertion of pair of directed edges (a,b) and (b,a) . We first state the following immediate corollary of Lemma 26 . Lemma 34 ( [ FF56 ] ) . Upon insertion of an edge e in G , the value of maximum (s,t) -flow can increase in G\cup\{e\} if and only if there is an (s,t) -path in (G^{f}\cup\{e\}) . The following lemma shows that \mathcal{D}_{PQ}(G) can be used to report an (s,t) -mincut after the insertion of a single edge in \mathcal{O}(n) time. Lemma 35 ( [ PQ80 ] and Lemma 4.4 in [ BBP23 ] ) . For any undirected multi-graph \mathcal{G} , upon the insertion of any edge e=(u,v) , the capacity of (s,t) -mincut increases by 1 if and only if u is mapped to sink \mathbb{S} and v is mapped to source \mathbb{T} or vice-versa in {\mathcal{D}}_{PQ}(\mathcal{G}) . Moreover, the set of vertices mapped to \mathbb{S} defines an (s,t) -mincut in \mathcal{G}\cup\{e\} . Similar to handling the failure of edges in Appendix F.2 , our main objective is to construct \mathcal{D}_{PQ}(G\cup\{e_{1}\}) by only using DAG \mathcal{D}(\mathcal{A}) and set of edges \mathcal{A} from Theorem 4 . Using the fact \mathcal{D}(\mathcal{A})\cup\mathcal{A} is a quotient graph of G^{f} , along a similar lines to the proof of Lemma 29 , we can establish the followin lemma. Lemma 36 . Upon the insertion of any edge e in G^{f} , there exists an (s,t) -path P_{r} in G^{f}\cup\{e\} if and only if there exists an (s,t) -path P in (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e\} . Moreover, P is a quotient path of P_{r} . We now use (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e_{1}\} to determine whether flow f is also a maximum (s,t) -flow in G\cup\{e_{1}\} or whether its value can increase by 1 . We verify whether there exists an (s,t) -path P in graph (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e_{1}\} . Suppose path P exists. It follows from Lemma 36 that there is an (s,t) -path P_{r} in G^{f} such that P is a quotient path of P_{r} . So, by Lemma 34 , the capacity of (s,t) -mincut is \lambda+1 in G\cup\{e_{1}\} . Upon updating path P_{r} in G^{f} by following the construction of residual graph, let f_{2} be the maximum (s,t) -flow of value \lambda+1 obtained in G\cup\{e_{1}\} and let G^{f_{2}} be the corresponding residual graph. Since \mathcal{D}(\mathcal{A})\cup\mathcal{A} is a quotient graph of G^{f} , instead of updating P_{r} , we update path P in (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e_{1}\} by following the construction of residual graph (refer to Section 3 ) to obtain graph D_{2} . The above steps can be executed in {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) time. If there exists no (s,t) -path in (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e_{1}\} , then D_{2} is the same as (\mathcal{D}(\mathcal{A})\cup\mathcal{A})\cup\{e_{1}\} , G^{f_{2}}=G^{f} , and the capacity of (s,t) -mincut is \lambda in G\cup\{e_{1}\} . We now establish the following relation between graph D_{2} and G^{f_{2}} . Lemma 37 . Graph D_{2} satisfies the following three properties. 1. D_{2} is a quotient graph of G^{f_{2}} , where f_{2} is a maximum (s,t) -flow in G\cup\{e_{1}\} . 2. A pair of vertices u,v are mapped to the same node in {\mathcal{D}}({\mathcal{A}}) if and only if u,v are mapped to the same node in D_{2} . 3. If a pair of vertices u,v is mapped to a node in D_{2} then u,v belong to the same SCC in G^{f_{2}} . Proof. The proof of properties (1) and (2) follows directly from the construction of D_{2} . We now establish the property (3) of D_{2} . Suppose u,v are a pair of vertices that are mapped to the same node in D_{2} . It follows from Theorem 4 that any (s,t) -cut that separates u,v has capacity at least \lambda+2 in G . Insertion of edge e_{1} can only increase the capacity of any (s,t) -cut. Therefore, by property (2), the least capacity (s,t) -cut in G\cup\{e_{1}\} that separates vertices u,v has capacity at least \lambda+2 . Moreover, the capacity of (s,t) -mincut in G\cup\{e_{1}\} is at most \lambda+1 . Therefore, by Lemma 3 , u,v are mapped to the same node in \mathcal{D}_{PQ}(G\cup\{e_{1}\}) . By construction of \mathcal{D}_{PQ}(G\cup\{e_{1}\}) , u,v belong to the same SCC in G^{f_{2}} . ∎ We now obtain DAG {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) from graph D_{2} . Let {\mathcal{I}} be the graph obtained by contracting every SCC of D_{2} . The following relation between {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) and {\mathcal{I}} can be established along similar lines to Lemma 32 using Lemma 37 . Lemma 38 . A pair of vertices u,v are mapped to the same node in {\mathcal{I}} if and only if u,v are mapped to the same node in {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) . It follows from Lemma 37 (1) and Lemma 38 that the set of edges in \mathcal{I} is the same as the set of edges in {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) . Therefore, the following lemma is immediate. Lemma 39 . Graph {\mathcal{I}} is the graph \mathcal{D}_{PQ}(G\cup\{e_{1}\}) . It follows from Lemma 39 that given {\mathcal{D}}({\mathcal{A}}) and set of edges {\mathcal{A}} , there is an algorithm that, using {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) space, can compute graph {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) in {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time. Hence, we can use Lemma 35 to check whether the insertion of edge e_{2} in G\cup\{e_{1}\} increases the capacity of (s,t) -mincut. Suppose e_{2} satisfies the condition stated in Lemma 35 for \mathcal{D}_{PQ}(G\cup\{e_{1}\}) . If the (s,t) -mincut capacity in G\cup\{e_{1}\} is \lambda+1 (likewise \lambda ), then after the insertion of two edges e_{1},e_{2} , the capacity of (s,t) -mincut in G is \lambda+2 (likewise \lambda+1 ). If e_{2} fails to satisfy the condition stated in Lemma 35 for {\mathcal{D}}_{PQ}(G\cup\{e_{1}\}) , the capacity of (s,t) -mincut in G after the insertion of edges e_{1},e_{2} is the same as the capacity of (s,t) -mincut in G\cup\{e_{1}\} . Moreover, the reported (s,t) -mincut using Lemma 35 in \mathcal{D}_{PQ}(G\cup\{e_{1}\}) is also an (s,t) -mincut in G after the insertion of two edges e_{1},e_{2} . Therefore, overall {\mathcal{O}}(\min\{{m,n\sqrt{\lambda}}\}) time is required to report an (s,t) -mincut and its capacity after the insertion of edges e_{1},e_{2} in graph G . This leads to the following theorem. Theorem 14 (Dual Edge Insertions for Simple Graphs) . Let G be an simple graph on n vertices and m edges with designated source and sink vertices s and t respectively. There exists a data structure occupying {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) space that can report an (s,t) -mincut in {\mathcal{O}}(\min\{m,n\sqrt{\lambda}\}) time after the insertion of any pair of given query edges in G . Appendix H Computing Minimum+1 (s,t)-cut in Directed Multi-graphs For graphs with integer edge capacities, Gabow [ Gab91 ] designed an algorithm that takes \tilde{{\mathcal{O}}}(m\lambda) time to compute a global mincut. By using this algorithm of [ Gab91 ] and our result in Theorem 2 (1), we immediately arrive at the algorithm stated in the following theorem. Theorem 15 . For any directed multi-graph on n vertices and m edges with designated source and sink vertices s and t respectively, there is an algorithm that, given any maximum (s,t) -flow, can compute a second (s,t) -mincut of capacity \lambda+\kappa , where \kappa\geq 0 is an integer, in \tilde{{\mathcal{O}}}(m\kappa) time. Let us consider graph G to be a directed multi-graph for this section. Suppose there is a (\lambda+1) (s,t) -cut in G . It follows that the capacity of second (s,t) -mincut is \lambda+1 in G . By Theorem 15 with \kappa=1 , given any maximum (s,t) -flow, we can compute a (\lambda+1) (s,t) -cut in G in \tilde{{\mathcal{O}}}(m) time. We now present an algorithm that given any maximum (s,t) -flow in G , can compute a (\lambda+1) (s,t) -cut, if it exists, in only {\mathcal{O}}(m) time. Our algorithm uses a different, as well as simpler, approach compared to the algorithm in Theorem 15 that uses the global mincut computation of [ Gab91 ] in directed graphs. Moreover, the insights established to arrive at our algorithm pave the way to compute all the anchor edges in undirected multi-graphs in {\mathcal{O}}(m) time (refer to Section I ). Along a similar line to the design of Algorithm 1 stated in Theorem 1 , given a second (s,t) -mincut in a graph with at most two (s,t) -mincuts \{s\} and V\setminus\{t\} , we can design an algorithm that can compute a second (s,t) -mincut in {\mathcal{O}}(m) time for graph G (refer to Appendix D.3 ). So, for the rest of the section, we assume that graph G has at most two (s,t) -mincuts \{s\} and V\setminus\{t\} . The following concept of (A,B) -mincut for sets A,B\subset V is defined for better exposition of our result. Definition 5 (( A,B )-mincut) . For any pair of sets \emptyset\subset A,B\subset V with A\cap B=\emptyset , a cut C is said to be an (A,B) -cut if A\subseteq C and B\subseteq\overline{C} . An (A,B) -mincut is an (A,B) -cut of the least capacity. H.1 Graphs with Exactly One (s,t)-mincut Suppose G has exactly one (s,t) -mincut V\setminus\{t\} . The algorithm is similar for graph G with (s,t) -mincut only \{s\} . For computing a (\lambda+1) (s,t) -cut, similar to the algorithm stated in Lemma 8 , we aim to efficiently find a vertex x\in V\setminus\{s,t\} , if exists, such that there is a (\lambda+1) (s,t) -cut C with x\in\overline{C} . We now establish a necessary and sufficient condition for identifying such a vertex x . Lemma 40 . For every vertex x\in V\setminus\{s,t\} , there is a (\lambda+1) (s,t) -cut C with x\in\overline{C} in G if and only if there is exactly one edge-disjoint path from s to x in G^{f} . Proof. Let the capacity of (s,x) -mincut be \lambda_{1} and (s,\{x,t\}) -mincut be \lambda_{2} . It follows that \lambda_{1}\leq\lambda_{2} . Let C be an (s,\{x,t\}) -mincut. Since t has indegree 0 , C\setminus\{t\} is an (s,x) -cut of capacity \lambda_{2} , and hence, \lambda_{2}\leq\lambda_{1} . It follows that \lambda_{1}=\lambda_{2} . If there is a (\lambda+1) (s,t) -cut C with x\in\overline{C} in G , by Theorem 10 , \lambda_{2}\leq 1 . Since V\setminus\{t\} is the only (s,t) -mincut in G^{f} , by Lemma 5 , \lambda_{2}=1 . This implies \lambda_{1}=1 and, by Menger’s theorem [ Men27 ] , the number of edge-disjoint paths from s to x is one. If there is exactly one edge-disjoint path from s to x in G^{f} , by Menger’s Theorem [ Men27 ] , \lambda_{1}=1 . Hence we get \lambda_{2}=1 , and by Theorem 10 , there exists a (\lambda+1) (s,t) -cut C with x\in\overline{C} in G . ∎ It follows from Lemma 40 that we only need to efficiently find a vertex x such that there is exactly one edge disjoint path from s to x in G^{f} . We use the concept of dominance with respect to vertex s to achieve this goal as follows. A vertex v is called a dominator of a vertex u if every (s,u) -path contains vertex v . A dominator tree of a graph is defined as follows. Theorem 16 (Dominator Tree [ LT79 ] ) . Let \mathcal{G} be any directed multi-graph. Let T_{\mathcal{G}} denote the dominator tree of \mathcal{G} on vertex set V with root vertex s . T_{\mathcal{G}} is a directed tree rooted at s such that the following property holds. For any pair of vertices u,v\in V , v is an ancestor of u in T_{\mathcal{G}} if and only if v is a dominator of u in \mathcal{G} . Observe that in graph G^{f} , there is exactly one edge-disjoint path from s to x if and only if there exists an edge e^{\prime} such that every (s,x) -path contains e^{\prime} . However, for any vertex u , even if v is a dominator of a vertex u , it is quite possible that there are more than one edge-disjoint (s,u) -paths in G^{f} . So, a dominator tree for G does not immediately help in determining whether there is exactly one edge-disjoint (s,u) -path in G^{f} . We now construct a graph \mathcal{H} from G^{f} whose dominator tree helps in achieving our objective. Construction of \mathcal{H}=(V^{\prime},E^{\prime}) : For each edge (u,v) in G^{f} , split edge (u,v) into two edges (u,w) and (w,v) using a new vertex w . It follows that the number of vertices, as well as edges, in \mathcal{H} is \mathcal{O}(m) . To design our algorithm, we begin by classifying the vertices in \mathcal{H} as follows. A vertex v\in V^{\prime} is said to be marked if v\notin V , otherwise, it is said to be unmarked . It follows from the construction of {\mathcal{H}} that there exists a marked vertex v in \mathcal{H} corresponding to every edge e^{\prime} in G^{f} and vice versa. Let T_{\mathcal{H}} be the dominator tree of \mathcal{H} with root vertex s . We now establish the following relation between T_{\mathcal{H}} and graph G^{f} . Lemma 41 . Let v be a marked vertex in \mathcal{H} corresponding to an edge e^{\prime} in G^{f} . v is an ancestor of an unmarked vertex u in T_{\mathcal{H}} if and only if every (s,u) -path contains e^{\prime} in G^{f} . Proof. Suppose marked vertex v is an ancestor of an unmarked vertex u in T_{\mathcal{H}} . It follows from Theorem 16 that each (s,u) -path in \mathcal{H} contains v . It follows from the construction of \mathcal{H} that each (s,u) -path contains the edge e^{\prime} (corresponding to v ) in G^{f} . Suppose u is an unmarked vertex and every (s,u) -path contains edge e^{\prime} in G^{f} . By construction of \mathcal{H} , every (s,u) -path contains marked vertex v (corresponding to edge e^{\prime} in G^{f} ) in \mathcal{H} . By Theorem 16 , v is ancestor of u in T_{\mathcal{H}} . ∎ We now use Lemma 41 to establish a relation between the dominator tree T_{\mathcal{H}} and (\lambda+1) (s,t) -cuts in graph G . Lemma 42 . Let v be a marked vertex in \mathcal{H} and let the edge in G^{f} corresponding to v be e^{\prime}=(w,u) . v is an internal vertex in T_{\mathcal{H}} with child u if and only if there exists a (\lambda+1) (s,t) -cut C in G such that the only edge outgoing from C in G^{f} is edge e^{\prime} . Proof. Suppose v is an internal marked vertex in T_{\mathcal{H}} with child u . By construction of \mathcal{H} , u is an unmarked vertex, since e^{\prime}=(w,u) in G^{f} . By Lemma 41 , every (s,u) -path contains edge (w,u) in G^{f} . Therefore, it is easy to show that the least capacity (s,t) -cut in G^{f} that separates \{s,w\} from \{u,t\} has capacity one, since t has indegree 0 . By Theorem 10 , C is a (\lambda+1) (s,t) -cut in G with u\in\overline{C} such that only e^{\prime} contributes to C in G^{f} . Suppose there exists a (\lambda+1) (s,t) -cut C in G such that the only edge outgoing from C in G^{f} is edge e^{\prime} . Since u\in\overline{C} , it follows that every (s,u) -path must contain edge e^{\prime} in G^{f} . By Lemma 41 , v is an ancestor of u (unmarked vertex) in T_{\mathcal{H}} . By construction of \mathcal{H} , (v,u) is an edge in \mathcal{H} . Hence, v is the parent of u in T_{\mathcal{H}} . ∎ Now, we state the algorithm for computing a (\lambda+1) (s,t) -cut in G . Algorithm: The algorithm begins by computing G^{f} and graph \mathcal{H} using maximum (s,t) -flow f in G . Compute the dominator tree T_{\mathcal{H}} from \mathcal{H} using the {\mathcal{O}}(m) time algorithm given in [ AHLT99 ] . To determine the existence of a (\lambda+1) (s,t) -cut in G , find a marked internal vertex in T_{\mathcal{H}} . If there does not exist any marked internal vertex in T_{\mathcal{H}} , by Lemma 42 , there exists no (\lambda+1) (s,t) -cut in G and the algorithm terminates. Suppose there exists an internal marked vertex v in T_{\mathcal{H}} with child u . By Lemma 42 , there is a (\lambda+1) (s,t) -cut C in G such that u\in\overline{C} . Obtain graph G_{u} from graph G^{f} by adding a pair of edges between u and t . Compute a maximum (s,t) -flow in graph G_{u} using the algorithm of Ford and Fulkerson [ FF56 ] . This completes the proof of the following lemma. Lemma 43 . Let G be a graph with exactly one (s,t) -mincut V\setminus\{t\} ( or \{s\}) . There is an algorithm that, given a maximum (s,t) -flow, computes a (\lambda+1) (s,t) -cut in G in \mathcal{O}(m) time. H.2 Graphs with Exactly two (s,t)-mincuts Lemma 40 fails to hold when G has exactly 2 (s,t) -mincuts: \{s\} and V\setminus\{t\} . This is because s has outdegree 0 in the residual graph G^{f} and there is no path from s to any vertex. Similar to the proof of Lemma 8 , we can address this problem by constructing the pair of graphs G^{I} and G^{U} (as constructed in the algorithm for second (s,t) -mincut stated in Lemma 8 ) using the covering technique of [ BBP23 ] . It follows that Lemma 43 is satisfied in both the graphs G^{I} and G^{U} . This leads to the following lemma. Lemma 44 . Let G be any graph with exactly two (s,t) -mincuts \{s\} and V\setminus\{t\} . There is an algorithm that, given a maximum (s,t) -flow, computes a (\lambda+1) (s,t) -cut in G in \mathcal{O}(m) time. Using Lemma 43 and Lemma 44 , we can compute a (\lambda+1) (s,t) -cut in general graphs as shown in Appendix D.3 with the following slight modification. Instead of working with each SCC H , here we compute (\lambda+1) (s,t) -cuts in the graph G_{\mu} constructed for the node \mu of {\mathcal{D}}_{PQ}(G) corresponding to H (refer to Appendix D.3 ). Observe that each edge (\mu_{1},\mu_{2}) in \mathcal{D}_{PQ}(G) appears in exactly two graphs – G_{\mu_{1}} and G_{\mu_{2}} . Moreover, due to the use of Covering Technique [ BBP23 ] , each edge and vertex in G_{\mu} is counted at most twice. Hence, the total number of vertices and edges across all graphs G_{\mu} are \mathcal{O}(n) and \mathcal{O}(m) respectively. This completes the proof of Theorem 3 . Appendix I Computation of All Anchor Edges in Undirected Multi-Graphs In this section, we design an efficient algorithm to compute the set of all anchor edges \mathcal{A} in an undirected multi-graph for any fixed maximum (s,t) -flow f . It follows from Lemma 48 and Definition 4 that no anchor edge appears in \mathcal{D}_{PQ}(G) since f(e)=0 . By Lemma 3 and the construction of \mathcal{D}_{PQ}(G) , the following lemma is immediate. Lemma 45 . If (u,v)\in\mathcal{A} then u and v are mapped to the same SCC in G^{f}. It follows from Lemma 45 that set of edges \mathcal{A} can be partitioned based on the nodes to which they are mapped. Hence, we now provide the construction of a graph G_{\mu}^{U} to compute all the edges belonging to \mathcal{A} whose endpoints are mapped to node \mu in \mathcal{D}_{PQ}(G) . The construction of G_{\mu}^{U} is the same as G_{\mu} but the contraction of vertices is done in G instead of G^{f} by exploiting the topological ordering of DAG \mathcal{D}_{PQ}(G) . Construction of G_{\mu} : Let \tau be a topological ordering of nodes in \mathcal{D}_{PQ}(G) that begins with {\mathbb{T}} and ends with {\mathbb{S}} . Graph G_{\mu}^{U} is obtained by modifying graph G as follows. The set of vertices mapped to the nodes that precede \mu in \tau is contracted into a sink vertex t^{\prime} . Similarly, the set of vertices mapped to the nodes that succeed \mu in \tau is contracted into source vertex s^{\prime} . If \mu=\mathbb{S} (likewise \mathbb{T} ), then we map exactly s to s^{\prime} (likewise t to t^{\prime} ). Without causing ambiguity, we denote an (s^{\prime},t^{\prime}) -cut in G_{\mu}^{U} by an (s,t) -cut. By Lemma 45 and the construction of G_{\mu}^{U} , the following lemma is immediate. Lemma 46 . In graph G_{\mu}^{U} , the following assertions hold. 1. The capacity of (s,t) -mincut is \lambda . 2. There are at most two (s,t) -mincuts – \{s\} and V\setminus\{t\} . 3. For any edge (u,v)\in\mathcal{A} , u and v are mapped to node \mu if and only if (u,v) is an anchor edge in G_{\mu}^{U} . It is evident from Lemma 46 that we need to identify anchor edges in graphs with at most two (s,t) -mincuts \{s\} and V\setminus\{t\} . Moreover, by the use of covering technique [ BBP23 ] , we only need to identify anchor edges in graphs with exactly one (s,t) -mincut \{s\} or V\setminus\{t\} . Consider G to be an undirected multi-graph with exactly one (s,t) -mincut V\setminus\{t\} . The algorithm is similar when the only (s,t) -mincut is \{s\} . Consider the graph \mathcal{H} constructed from G^{f} in Appendix H.1 . We now establish a relation between the anchor edges and the internal marked vertices in the dominator tree T_{\mathcal{H}} . Lemma 47 . Let T_{\mathcal{H}} be the dominator tree for graph \mathcal{H} . Suppose v is a marked vertex in \mathcal{H} and the edge corresponding to v in G^{f} is e^{\prime}=(w,u) . v is an internal vertex with a child u in T_{\mathcal{H}} if and only if the undirected edge (w,u) corresponding to e^{\prime} is an anchor edge in G and there is a (\lambda+1) (s,t) -cut C with w\in C,u\in\overline{C} . Proof. Suppose v is an internal vertex in T_{\mathcal{H}} with child u . It follows from Lemma 42 that there exists a (\lambda+1) (s,t) -cut C in G such that the edge e^{\prime}=(w,u) contributes to C in G^{f} . Hence, w\in C,u\in\overline{C} . It follows from Theorem 9 and the construction of G^{f} that the undirected edge (w,u) in G (corresponding to e^{\prime} ) carries zero flow. It follows from Theorem 9 and Lemma 19 that the edge carrying zero flow in the edge-set of C is an anchor edge. Hence, edge (w,u) is an anchor edge in G . Suppose the edge (w,u) is an anchor edge in G and there is a (\lambda+1) (s,t) -cut C in G with w\in C,u\in\overline{C} . By construction of G^{f} and Theorem 9 , exactly e^{\prime}=(w,u) contributes to C in G^{f} . By Lemma 42 , marked vertex v corresponding to edge e^{\prime} in G^{f} is an internal vertex in T_{\mathcal{H}} with child u . ∎ Lemma 47 implies that it is sufficient to compute all the internal marked vertices in T_{\mathcal{H}} corresponding to graph G_{\mu}^{U} for each node \mu in \mathcal{D}_{PQ}(G) . Similar to the analysis of the algorithm for computing a (\lambda+1) (s,t) -cut (refer to Appendix H.2 ), it can be established that we can compute set {\mathcal{A}} in {\mathcal{O}}(m) time. Appendix J Space Occupied by \mathcal{D}(G\setminus\mathcal{A}) in Undirected Multi-graphs In this section, we establish an upper bound on the space required by \mathcal{D}_{PQ} for undirected multi-graphs using only existing results. We first state the following property for \mathcal{D}_{PQ} which holds for undirected graphs. Lemma 48 ( [ PQ80 , FF56 ] ) . Let f be any maximum (s,t) -flow in any undirected graph {G} . For any edge e=(x,y) in {\mathcal{D}}_{PQ}({G}) , the corresponding undirected edge e in {G} satisfies f(e)=w(e) and e carries flow in the direction y to x . An (s,t) -flow is said to be acyclic if there is no directed cycle in which every edge carries flow in the direction of the cycle. For any integral acyclic maximum (s,t) -flow in an undirected integer-weighted graph, the number of edges carrying flow is bounded by the following lemma. Lemma 49 ( [ GY95 ] and Lemma 12 in [ GH23 ] ) . Let {G} be any undirected integer-weighted graph with no parallel edges and (s,t) -mincut capacity \lambda . For any integral acyclic maximum (s,t) -flow in {G} , the number of edges carrying flow in {G} is \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) . It follows from Lemma 48 that for every edge e of {\mathcal{D}}_{PQ}({\mathcal{G}}) , the corresponding undirected edge e carries flow in any maximum (s,t) -flow in {\mathcal{G}} . As a result, they also carry flow in any integral acyclic maximum (s,t) -flow. Therefore, the following lemma is immediate from Lemma 49 . Lemma 50 . For any undirected integer-weighted graph {G} with (s,t) -mincut capacity \lambda , the space occupied by DAG \mathcal{D}_{PQ}({G}) is \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) . We can easily transform any undirected multi-graph G to an undirected integer-weighted graph G^{\prime} with no parallel edges as follows. For any pair u,v , if there are q edges, q>0 , between u and v , then replace all these edges with a single edge (u,v) of capacity q . Observe that for each cut C , C has capacity \lambda^{\prime} in G if and only if C has capacity \lambda^{\prime} in G^{\prime} . Hence, for any undirected multigraph G , we can use \mathcal{D}_{PQ}(G^{\prime}) to store and characterize all (s,t) -mincuts in G . This, along with Lemma 50 , gives us the following result. Lemma 51 . For any undirected multi-graph {G} with (s,t) -mincut capacity \lambda , there is an undirected integer-weighted graph {G^{\prime}} with no parallel edges such that 1. the capacity of each cut in G remains the same in G^{\prime} and 2. DAG \mathcal{D}_{PQ}(G^{\prime}) occupies \mathcal{O}(\min\{m,n\sqrt{\lambda}\}) space.