Minimum Cuts in Directed Graphs via $\sqrt{n}$ Max-Flows

The minimum cut (or mincut) problem is one of the most widely studied problems in graph algorithms. In directed graphs (or digraphs), the goal of this problem is to find a minimum weight set of edges whose removal creates multiple strongly connected components in the graph. Equivalently, a minimum cut of a digraph is a bipartition of the vertices into two non-empty sets $(S,V\setminus S)$ such that the weight of edges from $S$ to $V\setminus S$ is minimized. This problem can be solved by using $O(n)$ maxflow calls by finding the minimum among all the $r-v$ mincuts and $v-r$ mincuts for all vertices $v\not=r$. In a beautiful result, Hao and Orlin [HO94] showed that these maxflow calls can be amortized to match the running time of only polylog($n$) calls to the push-relabel maxflow algorithm [GT88]. This leads to an overall running time of $\tilde{O}(mn)$ on an $m$-edge, $n$-vertex graph. Since their work, better maxflow algorithms have been designed (e.g., Goldberg and Rao [GR98]), but the amortization does not work for these algorithms. Using a different technique of duality between rooted mincuts and arborescences, Gabow [Gab95] obtained a running time of $\tilde{O}(m\lambda)$ for this problem, where $\lambda$ is the weight of a mincut (assuming integer weights). This is at least as good as the Hao-Orlin running time for unweighted simple graphs, but can be much worse for weighted graphs. Indeed, the Hao-Orlin bound of $\tilde{O}(mn)$ remains the state of the art for the directed mincut problem on arbitrary weighted graphs.

In this paper, we give an algorithm for the directed mincut problem that has a time complexity of $O(\sqrt{n})$ maxflow calls. Importantly, and unlike the Hao-Orlin algorithm, our algorithm can use any maxflow algorithm; in fact, it treats the maxflow algorithm as a black box. Using state of the art max flow algorithms that run in $\tilde{O}(m+n^{3/2})$ time [vdBLL⁺21], this yields a directed mincut algorithm in $\tilde{O}(m\sqrt{n}+n^{2})$ time, thereby improving on the Hao-Orlin bound. Moreover, if one were to believe the widely held conjecture that maxflow would eventually be solved in $\tilde{O}(m)$ time, then the running time of our algorithm would automatically become $\tilde{O}(m\sqrt{n})$.

Given a directed graph $G=(V,E)$ with non-negative edge weights $w$, we consider the problem of finding a (global) minimum directed cut in this graph. For simplicity, we assume that all edge weights $w$ are integers and are polynomially bounded. We denote $\overline{U}=V\setminus U$. Let $\partial U$ be the set of edges in the cut $(U,\overline{U})$, and let $\delta(U)$ be the weight of the cut, i.e., $\delta(U)=\sum_{e\in\partial U}w(e)$. Our goal is to find $\arg\min_{\emptyset\subset U\subset V}\delta(U)$. Let $MF(m,n)$ denote the time complexity of $s$-$t$ maximum flow on a digraph with $n$ vertices and $m$ edges. The current record for this bound is $MF(m,n)=\tilde{O}(m+n^{3/2})$ [vdBLL⁺21]. We emphasize that our directed mincut algorithm uses maxflow subroutines in a black box manner and therefore, any maxflow algorithm suffices. Correspondingly, we express our running times in terms of $MF(m,n)$.

Next we describe the algorithm. Let $S^{*}$ be the source side of a minimum cut. The algorithm considers the following two cases, computes a cut for each case and takes the smaller of the two cuts as its final output.

1. 1.

   The first case aims to compute the correct mincut in the event that $\min\{|S^{*}|,|\overline{S^{*}}|\}>\theta\cdot\sqrt{n}/\log n$. In this case, we randomly sample two vertices $s,t\in V$, then with reasonable probability, they will lie on opposite sides of the mincut. In that case, we can simply compute the maxflow from $s$ to $t$. Repeating the sampling $O(\sqrt{n}\log^{2}n)$ times, we obtain the mincut whp. The total running time for this case is $O(MF(m,n)\sqrt{n}\log^{2}n)$ and is formalized in Lemma 2 below:

   Lemma 2.

   If $\min\{|S^{*}|,|\overline{S^{*}}|\}>r$, then whp a mincut can be calculated in time $O(MF(m,n)\cdot(n/r)\cdot\log n)$.

   Proof.

   Uniformly sample a list of $k=d\cdot(n/r)\cdot\lg n$ vertices $u_{1},\ldots,u_{k}$, where $d$ is a large constant. Wlog, assume $|S^{*}|\leq|\overline{S^{*}}|$, and let $\eta=\frac{|S^{*}|}{n}>\frac{r}{n}$. With probability at least $1-2(1-\eta)^{k}\geq 1-2e^{-k\eta}\geq 1-2n^{-d}$, the list $u_{1},\ldots,u_{k}$ contains at least one vertex from each of $S^{*}$ and $\overline{S^{*}}$. Hence, there exists $i$ such that $u_{i}$ and $u_{i+1}$ are on different sides of the $(S^{*},\overline{S^{*}})$ cut. By calculating maxflows for all ($u_{i}$, $u_{i+1}$) and ($u_{i+1}$, $u_{i}$) pairs, and reporting the smallest $s-t$ mincut in these calls, we return a global mincut whp. ∎

2. 2.

   The second case takes care of the event that $\min\{|S^{*}|,|\overline{S^{*}}|\}\leq\theta\cdot\sqrt{n}/\log n$. In this case, we select an arbitrary vertex $s$, and give an algorithm for finding an $s$-mincut defined as:

   Definition 3.

   An $s$-mincut is a minimum weight cut among all those that have $s$ on the source side of the cut, i.e., $\arg\min_{\{s\}\subseteq S\subset V}\delta(S)$.

   Repeating this process with all edge directions reversed, and returning the smaller of the $s$-mincuts in the original and the reversed graphs, yields the overall mincut.

   We now describe the $s$-mincut algorithm, where we overload notation to denote the value of the $s$-mincut by $\lambda$. Here, we first guess $O(\log n)$ potential values of $\tilde{\lambda}$, which is our estimate of $\lambda$, as the powers of $2$, one of which lies in the range $[\lambda,2\lambda]$, and then for each $\tilde{\lambda}$, sparsifies the graph using Lemma 7 from Section 3. For each such sparsifier $H$, the algorithm then applies Lemma 8 from Section 4 to pack $O(\log n)$ $s$-arborescences in $H$ in $O(m\sqrt{n}\log n)$ time, one of which will $1$-respect the $s$-mincut in $G$ (for the correct value of $\tilde{\lambda}$):

   Definition 4.

   An $s$-arborescence is a directed spanning tree rooted at $s$ such that all edges are directed away from $s$. A directed $s$-cut $k$-respects an $s$-arborescence if there are at most $k$ cut edges in the arborescence.

   Finally, for each of the $O(\log n)$ $s$-arborescences, the algorithm computes the minimum $s$-cut that $1$-respects each arborescence; this algorithm is described in Algorithm 1 and proved in Theorem 12 from Section 5. It runs in $O((MF(m,n)+m)\cdot\log n)$ time for each of the $O(\log n)$ arborescences.

Combining both cases, the total running time becomes $\tilde{O}(m\sqrt{n}+MF(m,n)\sqrt{n})$, which establishes Theorem 1.

This section aims to reduce mincut value to $\tilde{O}(\sqrt{n})$ while keeping $S^{*}$ a $(1+\epsilon)$-approximate mincut for a constant $\epsilon>0$ that we will fix later. Our algorithm in this stage has two steps. First, we use random sampling to scale down the expected value of all cuts such that the expected value of the mincut $\delta(S^{*})$ becomes $\tilde{O}(\sqrt{n})$. We also claim that $\partial S^{*}$ remains an approximate mincut among all unbalanced cuts by using standard concentration inequalities. However, since the number of balanced cuts far exceeds that of unbalanced cuts, it might be the case that some balanced cut has now become much smaller in weight than all the unbalanced cuts. This would violate the requirement that $\partial S^{*}$ should be an approximate mincut in this new graph. This is where we need our second step, where we overlay an expander on the sampled graph to raise the values of all balanced cuts above the expected value of $\partial S^{*}$ while only increasing the value of $\partial S^{*}$ by a small factor. This last technique is inspired by recent work of Li [Li21] for a deterministic mincut algorithm in undirected graphs.

We start with the specific expansion properties that we need, and a pointer to an existing construction of such an expander.

Now, we prove the main property of this section:

In this section, we assume that there is an unbalanced mincut and show how to obtain an $s$-arborescence that 1-respects the mincut. More formally, we prove the following:

The idea of this lemma is as follows. First, we apply Lemma 7 to our graph $G$ and obtain graph $H$. Whp, a mincut $S^{*}$ in $G$ corresponds to a cut in $H$ of size $(1\pm\epsilon)p\lambda$ and no cut in $H$ has size less than $(1-\epsilon)p\lambda$. That is, $S^{*}$ is a $(1+O(\epsilon))$-approximate mincut in $H$. It remains to find an arborescence in $H$ that 1-respects $S^{*}$. To do this, we employ a multiplicative weight update (MWU) framework. The algorithm begins by setting all edge weights to be uniform (say, weight $1$). Then, we repeat for $O(\sqrt{n}\log(n)/\epsilon^{2})$ rounds. For each round, we find in near-linear time a minimum weight arborescence and multiplicatively increase the weight of every edge in the arborescence.

Using the fact that there is no duality gap between arborescence packing and mincut [Edm73, Gab95], a standard MWU analysis implies that these arborescences that we found, after some scaling, form a $(1+\epsilon)$-approximately optimal fractional arborescence packing. So our arborescence crosses $S^{*}$ at most $(1+O(\epsilon))<2$ times on average. Thus, if we sample $O(\log n)$ arborescences from our collections, whp, one of them will 1-respect $S^{*}$.⁴⁴4This should be compared with Karger’s mincut algorithm in the undirected case, where there is a factor $2$ gap, and hence Karger can only guarantee a $2$-respecting tree in the undirected case. Below, we formalize this high level description.

The fractional arborescence packing problem conforms to this definition. Enumerate all the $s$-arborescences as $A_{1},A_{2},\ldots,A_{N}$. We represent a fractional packing of arborescences as a vector in $\mathds{R}^{N}$, where coordinate $i$ represents the fractional contribution of $A_{i}$ in the packing. Let$P=\{x\in\mathds{R}^{N}:x^{T}1=1,x\geq 0\}$ be the convex hull of all single arborescences. For each edge $j$ with capacity $w(j)$, $f_{j}(x)=\sum_{i\in[N]}x_{i}1[j\in T_{i}]/w(j)$ is the relative load of arborescence packing $x$ on edge $j$. It is easy to see that $\omega\leq 1/w_{\min}$ for tree packing. The objective function is to minimize the maximum load: $\gamma^{*}=\min_{x\in P}\max_{j\in[m]}f_{j}(x)$.

For any fractional arborescence packing $x\in\mathds{R}^{N}$ with value $x^{T}1=v$ where $f_{j}(x)\leq 1$ for all edges $j$, we have $\frac{1}{v}x\in P$. In particular, the maximum arborescence packing, once scaled down by its value, is exactly the vector in $P$ that minimizes the maximum load. Therefore, it suffices to look for the vector $x\in P$ achieving the optimal value $\gamma^{*}$, and then scale the vector up by $1/\gamma^{*}$ to obtain the maximum arborescence packing.

Next we describe the packing algorithm (Figure 2 of [You95]). Maintain a vector $y\in\mathds{R}^{m}$, initially set to $y=1$. In each iteration, find $x=\arg\min_{x\in P}\sum_{j}y_{j}f_{j}(x)$, and then add $x$ to set $S$ and replace $y$ by the vector $y^{\prime}$ defined by $y^{\prime}_{j}=y_{j}(1+\epsilon f_{j}(x)/\omega)$. After a number of iterations, return $\bar{x}\in P$, the average of all the vectors $x$ over the course of the algorithm. The lemma below upper bounds the number of iterations that suffice:

We will also make use of the (exact) duality between $s$-arborescence packing and minimum $s$-cut:

We propose an algorithm (Algorithm 1) that uses $O(\log n)$ maxflow subroutines to find the minimum $s$-cut that $1$-respects a given $s$-arborescence. The result is formally stated in Theorem 12.

We first give some intuition for Algorithm 1. Because $s\in S$, if we could find a vertex $t\in\overline{S}$, then computing the $s$-$t$ mincut using one maxflow call would yield a global mincut of $G$. However, we cannot afford to run one maxflow between $s$ and every other vertex in $G$. Instead, we carefully partition the vertices into $\ell=O(\log n)$ sets $(C_{i})_{i=1}^{\ell}$. We show that for each $C_{i}$, we can modify the graph appropriately so that it allows us to (roughly speaking) compute the maximum flow between $s$ and every vertex $c\in C_{i}$ using one maxflow call.

More specifically, Algorithm 1 has two stages. In the first stage, we compute a centroid decomposition of $T$. Recall that a centroid of $T$ is a vertex whose removal disconnects $T$ into subtrees with at most $n/2$ vertices. This process is done recursively, starting with the root $s$ of $T$. We let $P_{1}$ denote the subtrees resulting from the removal of $s$ from $T$. In each subsequent step $i$, we compute the set $C_{i}$ of the centroids of the subtrees in $P_{i}$. We then remove the centroids and add the resulting subtrees to $P_{i+1}$. This process continues until no vertices remain.

In the second stage, for each layer $i$, we construct a directed graph $G_{i}$ and perform one maxflow computation on $G_{i}$. The maxflow computation on $G_{i}$ would yield candidate cuts for every vertex in $C_{i}$, and after computing the appropriate maximum flow across every layer, we output the minimum candidate cut as the minimum cut of $G$. The details are presented in Algorithm 1.

We first state two technical lemmas that we will use to prove Theorem 12.

We defer the proofs of Lemmas 13 and 14, and first use them to prove Theorem 12.

Before proving Lemmas 13 and 14 we first prove the following lemma.

Recall that Lemma 13 states that if all the centroids in previous layers are in $S$, then $\overline{S}$ is contained in exactly one subtree $U$ in the current layer $i$.

Next we prove Lemma 14, which states that the maximum flow between $s$ and $t_{i}$ in the modified graph $G_{i}$ allows one to simultaneously compute a candidate mincut value for each vertex $u\in C_{i}$.