Search Results

Let G be an undirected graph on a set V of n vertices. For any non-empty subset A⊊ V, cut defined by A is the ordered pair (A,V\A). Suppose each cut is assigned a value, which is any arbitrary real number. Let u,v ∈ V be any pair of vertices. A cut is said to be a (u,v)-cut if it separates u and v. A (u,v)-cut of the minimum value is called a (u,v)-mincut. A 2nd (u,v)-mincut is a (u,v)-cut of second minimum value. We can define k-th mincut accordingly. We present the following results for the all-pairs k-th mincuts. (1) Distinct Values of all-pairs k-th Mincuts: There exist k spanning trees on V such that for any pair (u,v), the value of k-th (u,v)-mincut is equal to the capacity of an edge on the (u,v)-path in one of the k trees. We also show a matching lower bound of Ω(min{kn,n²}). Our result generalizes the well-known result by Gomory and Hu [JSIAM 1961] stating that there are at most n-1 distinct values of all-pairs mincuts. (2) Ancestor Trees for all-pairs k-th Mincuts: In 1991, Cheng and Hu [AOR 1991] invented a rooted binary tree, called ancestor tree, whose leaves are the vertices of the graph and each internal node stores a cut with the following property. For any pair (u,v), the cut stored at their lowest common ancestor (LCA) is a (u,v)-mincut. We introduce a tree called gen-ancestor tree, that generalizes the ancestor tree for k-th mincuts, and achieve the following result. There exists a set of 𝒪(klog n) gen-ancestor trees such that, for any pair (u,v), a k-th (u,v)-mincut is stored at the LCA of u and v in at least one of these trees. (3) Data Structures: We present the following data structures for all-pairs k-th mincuts. (i) There exists an 𝒪(nlog n) space data structure that can report the value of 2nd (u,v)-mincut in 𝒪(log n) time for any given pair (u,v). We generalize this data structure for k-th mincuts with a factor of k² in the space and query time. (ii) There exists an 𝒪(kn² log n) space data structure that can report a k-th (u,v)-mincut (A,V\A) in 𝒪(|A|) time for any given pair (u,v). For any constant k, the bounds stated above match, up to a logarithmic factor, the best-known bounds guaranteed by the data structure for all-pairs mincuts (Cheng and Hu [AOR 1991]).

Let G be a directed graph on n vertices and m edges. In this article, we study (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)-cut of second minimum capacity using {O}(n²) maximum (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)-cut of second minimum capacity using Õ(√n) maximum (s,t)-flow computations with high probability. To achieve this result, a close relationship of independent interest is established between (s,t)-cuts of second minimum capacity and global mincuts in directed weighted graphs. 2) Minimum+1 (s,t)-cuts: Minimum+1 (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)-mincut. We present the following structural result and the first nontrivial algorithm for minimum+1 (s,t)-cuts. 3) Algorithm: For directed multi-graphs, we design an algorithm that, given any maximum (s,t)-flow, computes a minimum+1 (s,t)-cut, if it exists, in O(m) time. 4) Structure: The existing structures for storing and characterizing all minimum+1 (s,t)-cuts occupy {O}(mn) space [Baswana, Bhanja, and Pandey, TALG 2023]. For undirected multi-graphs, we design a directed acyclic graph (DAG) occupying only {O}(m) space that stores and characterizes all minimum+1 (s,t)-cuts. This matches the space bound of the widely-known DAG structure for all (s,t)-mincuts [Picard and Queyranne, Math. Prog. Studies 1980]. 5) 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)-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)-mincut in undirected multi-graphs must occupy Ω(n²) space in the worst-case irrespective of the query time. Interestingly, for undirected unweighted simple graphs, we break this quadratic barrier while achieving a non-trivial query time as follows. There is an O(n√n) space data structure that can report an (s,t)-mincut in O(min{m,n√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)-cuts of capacity (minimum+Δ), Δ ≥ 0, and maximum (s,t)-flow. We believe that these techniques and the graph-theoretic result in 2.(b) are of independent interest.