Faster Algorithm for Second (s,t)-Mincut and Breaking Quadratic Barrier for Dual Edge Sensitivity for (s,t)-Mincut

The concept of cut is fundamental in graph theory and has numerous real-world applications [1]. 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 [21, 19, 14, 25, 36]. In this article, 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 [37]. 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 undirected unweighted simple graphs¹¹1A simple graph refers to a graph having no parallel edges.. This breaks the existing quadratic lower bounds [3, 6] on the space for any dual edge sensitivity oracle for $(s,t)$-mincut in undirected multi-graphs²²2A 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 [3] by a linear factor.

We now present the problems addressed in this article, their state-of-the-art, and our results.

This article is organized as follows. Basic preliminaries and notations are stated in Section 3. A limitation of an existing algorithm in [37] for computing second $(s,t)$-mincut is provided in Section 4. In Section 5, we design two algorithms for computing a second (s,t)-mincut in directed weighted graphs. For undirected multi-graphs, in Section 6, 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 the following sections. For undirected multi-graphs, Section 7 contains the design of our linear space structure for storing and characterizing all $(\lambda +1)$ $(s,t)$-cuts. In Section 8, we design the subquadratic space dual edge sensitivity oracle for $(s,t)$-mincut in undirected unweighted simple graphs. Finally, we conclude in Section 9. All the omitted proofs are provided in the full version.

By integrality of maximum $(s,t)$-flow [19], for integer-weighted graphs, we consider any given maximum $(s,t)$-flow to be integral. The following notations to be used throughout the article.

• $\mathrm{■}$

  $G\cup A$ (likewise $G\setminus A$): Graph obtained after adding (likewise removing) a set of edges $A$ in $G$.

• $\mathrm{■}$

  $(\lambda +\mathrm{\Delta })$ $(s,t)$-cut: An $(s,t)$-cut of capacity $\lambda +\mathrm{\Delta }$ where $\mathrm{\Delta }\ge 0$.

• $\mathrm{■}$

  $(u,v)$-path : A simple directed path from vertex $u$ to vertex $v$.

• $\mathrm{■}$

  $f$ denotes a maximum $(s,t)$-flow in graph $G$.

• $\mathrm{■}$

  $c(C,H)$: Capacity of a cut $C$ in a graph $H$.

• $\mathrm{■}$

  A cut $C$ subdivides a set of vertices $X$ if $C\cap X\ne \mathrm{\varnothing }$ and $\overline{C}\cap X\ne \mathrm{\varnothing }$.

• $\mathrm{■}$

  A cut $C$ separates a pair of vertices $u,v$ if $u\in C$ and $v\in \overline{C}$ or vice-versa.

• $\mathrm{■}$

  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$.

• $\mathrm{■}$

  $H^{f^{\prime }}$ denotes the residual graph for any graph $H$ corresponding to an $(s,t)$-flow $f^{\prime }$.

• $\mathrm{■}$

  $f^{\prime }(e)$ denotes the value of flow $f^{\prime }$ assigned to an edge $e$.

• $\mathrm{■}$

  $f_{out}^{\prime }(C)$ and $f_{in}^{\prime }(C)$: For any $(s,t)$-cut $C$, $f_{out}^{\prime }(C)$ (likewise $f_{in}^{\prime }(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}$).

We state here a limitation of the existing algorithm given by Vazirani and Yannakakis [37] to compute a second $(s,t)$-mincut. The algorithm for computing an $(s,t)$-cut of $k^{th}$ minimum capacity by [37] uses $𝒪(n^{2(k-1)})$ maximum $(s,t)$-flows. So, for $k=2$, the algorithm uses $𝒪(n^2)$ maximum $(s,t)$-flow computations. In the same article [37], they stated the following property.

Vazirani and Yannakakis [37] used Lemma 14 to design an algorithm that computes second $(s,t)$-mincut using $𝒪(n)$ maximum $(s,t)$-flow computations (the algorithm preceding Theorem 3.3 in [37]). Unfortunately, Lemma 14 (or Lemma 3.2(1) in [37]) is not correct as shown in Figure 1$(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 14, 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 1$(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 [37], fails to correctly output a 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 $𝒪(n)$ maximum $(s,t)$-flow computations, which achieves the aim of Vazirani and Yannakakis [37]. This algorithm can be seen as an immediate application of the recently invented covering technique of [3]. We refer to the full version for the details of this algorithm. 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 $\widetilde{𝒪}(\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.

In a seminal work in 1956, Ford and Fulkerson [19] established a strong duality between $(s,t)$-mincut and maximum $(s,t)$-flow, which is widely known as the Maxflow-Mincut Theorem. We begin by stating the following property, which is immediate from Maxflow-Mincut Theorem.

It follows from Fact 15 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, Fact 15 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 and the construction of the residual graph, we provide a generalization of Fact 15 as follows.

The widely known Maxflow-Mincut Theorem [19] 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 [3]. Interestingly, we show that, in fact, there exist close relationships between maximum $(s,t)$-flow and $(\lambda +1)$ $(s,t)$-cuts as follows.

For undirected multi-graphs, we first establish the following property for $(\lambda +k)$ $(s,t)$-cuts, where $k\ge 0$ is an integer, based on a maximum $(s,t)$-flow.

We address the following problem for undirected multi-graphs in this section.

The problem of designing a compact structure for storing and characterizing all $(s,t)$-mincuts immediately reduces to Problem 22 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 [3] provide a solution to Problem 22 by essentially reducing it to the problem of designing a compact structure for storing and characterizing all $(s,t)$-mincuts. However, their structure occupies $𝒪(mn)$ space. For undirected multi-graphs, we present a structure for storing and characterizing all $(\lambda +1)$ $(s,t)$-cuts that occupies $𝒪(\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 3($i$)). In order to materialize the idea, we exploit Theorem 20, which motivates us to define a set of edges with respect to $(\lambda +1)$ $(s,t)$-cuts in the following way.

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 Theorem 20, 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 𝒜$. 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 𝒜$. However, using anchor edges $𝒜$, we can distinguish the $(\lambda +1)$ $(s,t)$-cuts as follows.

By Lemma 24, our compact structure consists of set of edges $𝒜$ and a structure that stores and characterizes all $(s,t)$-mincuts in $G\setminus 𝒜$. 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 $𝒜$. Therefore, we need to show that the set $𝒜$ is small.

In this section, for undirected unweighted 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 an undirected unweighted simple graph in this section. We provide an overview for handling the failure of edges in $G$. Note that handling the insertion of a pair of edges is along a similar line and is provided in the full version. 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 $𝒪(m)$ space dual edge sensitivity oracle for $(s,t)$-mincut that achieves $𝒪(m)$ query time. The query algorithm is derived from the augmenting path based algorithm for computing maximum $(s,t)$-flow by Ford and Fulkerson [19] (briefly explained as a warm-up below). However, it is known that the residual graph occupies quadratic space if $m=\mathrm{\Omega }(n^2)$. To design a subquadratic space dual edge sensitivity oracle for undirected unweighted simple graphs, instead of the residual graph $G^f$, we work with our compact structure, consisting of $𝒟$ and the set $𝒜$ of anchor edges, from Theorem 6. Recall that $𝒟$ is the graph ${𝒟}_{PQ}(G\setminus 𝒜)$, which is just a quotient graph of $G^f$. Hence, $𝒟\cup 𝒜$ may fail to preserve the complete information of every path in $G^f$. However, we show that $𝒟\cup 𝒜$ is still sufficient to answer dual edge failure queries using the same algorithm used for the folklore result using residual graph $G^f$.