We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tO(n\cdot \max(m^{2/3}, n))$ time. This improves on the 30 year old bound of $\tO(nm)$ obtained by Hao and Orlin for this problem. Our main technique is to reduce the directed mincut problem to $\tO(\min(n/m^{1/3}, \sqrt{n}))$ calls of any maxflow subroutine. Using state-of-the-art maxflow algorithms, this yields the above running time.

Our techniques also yield fast approximation algorithms for finding minimum cuts in directed graphs. For both  edge and vertex weighted graphs, we give $(1+\epsilon)$-approximation algorithms that run in $\tO(n^2 / \epsilon^2)$ time.

We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tO(n\cdot \max\{m^{2/3}, n\})$ time. This improves on the 30 year old bound of $\tO(nm)$ obtained by Hao and Orlin for this problem.  Using similar techniques, we also obtain $\tO(n^2 / \eps^2)$-time $(1+\eps)$-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs,
for any fixed $\epsilon$. Before our work, no $(1+\eps)$-approximation algorithm better than the exact runtime of $\tO(nm)$ is known for either problem.

Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to $\tO(\min\{n/m^{1/3}, \sqrt{n}\})$ calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

§ INTRODUCTION

The minimum cut (or mincut) problem is one of the most widely studied problems in graph algorithms. In (edge-)weighted[We assume throughout that edge/vertex weights are polynomially bounded integers.] directed graphs (or digraphs), a mincut is a bipartition of the vertices into two non-empty sets $(S, V\setminus S)$ so that the total weight of edges from $S$ to $V\setminus S$ is minimized.

This problem can be solved by solving the $s$-mincut problem (also called rooted mincut), where for a given root vertex $s$, we want to find the minimum weight cut $(S, V\setminus S)$ such that $s\in S$. (We call such cuts minimum $s$-cuts or $s$-mincuts.) This is because the mincut can be computed as the minimum between two $s$-mincuts for an arbitrary vertex $s$: one with the original edge directions in the input digraph, and the other with the edge directions reversed.

A simple algorithm for $s$-mincut (and thus mincut) on an $m$-edge, $n$-vertex digraph is to use $n-1$ maxflow calls to obtain the minimum $s-t$ cut for every vertex $t \not= s$ in the graph, and return the minimum among these. A beautiful result of Hao and Orlin [16] showed that these maxflow calls can be amortized to match the running time of a single maxflow call, provided one uses the  push-relabel maxflow algorithm [15]. This leads to an overall running time of $\tO(mn)$.
Since their work, better maxflow algorithms have been designed, but the amortization does not work for these algorithms.
As a consequence, the Hao-Orlin bound remains the best known for the directed mincut problem almost 30 years after their work.

This is too late now, but perhaps in the next version we can consider discussing undirected graphs and unwieghted graphs so the readers see the full picture. We should also discuss why it's much more challenging to attack weighted directed graphs.

Using a different technique of duality between rooted mincuts and arborescences, Gabow [9] obtained a running time of $\tO(m\lambda)$ for $s$-mincut, where $\lambda$ is the weight of a mincut (assuming integer weights).

For simple, unweighted graphs, we know $\lambda \le n-1$,
so Gabow's algorithm is no worse than Hao-Orlin, and sometimes better. Recently [3] obtained a randomized $\tO(n^2 U)$ time algorithm for integer capacities between $1$ and $U$.

For arbitrary weights, however, the the Hao-Orlin bound of $\tO(mn)$ remains the state of the art for the directed mincut problem.

I wrote the following to brief introduce vertex connectivity. I tried to keep it short. Otherwise it shows up for the first time in the results section which seems a little abrupt.
We also consider vertex connectivity in vertex-weighted digraphs. A vertex cut in a digraph is a set of vertices $X \subset V$ such that removing $X$ from the graph ensures that $G$ is not strongly connected (or consisting of a single vertex). The minimum vertex cut (or vertex mincut) problem is to find the vertex cut of minimum weight. One also has the rooted version of the problem where there is a fixed vertex $s$, and the goal is to compute the minimum weight set of vertices $X \subseteq V - \root$ such that either $X = V - \root$ or, after removing $X$, $\root$ is unable to reach at least one other vertex. Currently the fastest exact algorithm for minimum global and rooted vertex cut in weighted graphs is due to Henzinger, Rao, and Gabow [17] and runs in $\apxO{m n}$ randomized time. Interestingly this algorithm is based on the Hao-Orlin algorithm mentioned above. This bound has recently been improved for the special case of unweighted digraphs to $\tO(mn^{11/12+o(1)})$ [20].
This result is one of several recent developments for vertex connectivity in unweighted graphs as discussed below in <Ref>.

§.§ Our Results

In this paper, we can solve the $s$-mincut—thus the directed mincut problem—by essentially reducing it to $O(\sqrt{n})$ maxflow calls. At first glance, this is worse than the Hao-Orlin algorithm that only uses a single maxflow call. But crucially, while the Hao-Orlin algorithm is restricted to a specific maxflow subroutine and therefore cannot take advantage of faster, more recent maxflow algorithms, our new algorithm treats the maxflow subroutine as a black box, thereby allowing the use of any maxflow algorithm. Using state of the art maxflow algorithms that run in $\tO(m+n^{3/2})$ time [28], this already improves on the Hao-Orlin bound.
Using some additional ideas, we further reduce to $O(\min\{n/m^{1/3}, \sqrt{n}\})$ maxflow calls, which yields our eventual running time of $\tO(nm^{2/3} + n^2)$:

There is a randomized Monte Carlo algorithm that solves $s$-mincut (and therefore directed mincut) whp in $\tO(nm^{2/3} + n^2)$ time on an $n$-vertex, $m$-edge (edge-weighted) directed graph.

In fact, our reduction in general implies
a running time bound of $\tO(\min\{mk, nk^2\}+\frac{n}{k}\cdot F(m,n))$, where $k$ is a parameter that we can choose and $F(m,n)$ is the time complexity of maxflow (see <Ref>).

Our techniques also yield fast approximations for the mincut problem in directed graphs. In particular, for any $\epsilon\in(0, 1)$, we can find a $(1+\epsilon)$-approximate mincut in $\tO(n^2/\epsilon^2)$ time:

For any $\epsilon \in (0,1)$, there is a randomized Monte Carlo algorithm that finds a $(1+\epsilon)$-approximate $s$-mincut (and therefore directed mincut) whp in $\tO(n^2 / \epsilon^2)$ time on an $n$-vertex (edge-weighted) directed graph.

Finally, we consider vertex-weighted digraphs. A vertex cut in a digraph is defined as a tri-partition of vertices into sets $(L,X,R)$ such that there is no edge from $L$ to $R$. Should we say $L, R \not= \emptyset$? (In other words, removing the vertices in $X$ results in a digraph where the directed cut $(L, R)$ is empty.) A minimum vertex cut (or vertex mincut) is a vertex cut $(L, X, R)$ that minimizes the sum of weights of vertices in $X$. We give an algorithm to find a $(1+\epsilon)$-approximate vertex mincut in $\tO(n^2/\epsilon^2)$ time:

For any $\epsilon \in (0,1)$, there is a randomized Monte Carlo algorithm that finds a $(1+\epsilon)$-approximate minimum vertex $s$-cut and the minimum global vertex cut whp in $\tO(n^2 / \epsilon^2)$ time on an $n$-vertex (vertex-weighted) directed graph.

To the best of our knowledge, before this work, the fastest algorithms for $(1+\epsilon)$-approximation of mincuts in edge or vertex weighted directed graphs were the respective exact algorithms themselves, which obtained a running time of $\tO(mn)$ [16, 17].

Our approximation results establish a separation between the best exact and $(1+\epsilon)$-approximation algorithms for both edge and vertex mincut problems in directed graphs.

Our results are the first to

break the $O(mn)$ barrier for directed mincut problems in general, weighted digraphs. For all values of $m$ except when $m = n^{1+o(1)}$, this is immediate from the above theorems. If $m = n^{1+o(1)}$, we can also break the $O(mn)$ barrier by employing the recent $\apxO{m^{1.5 - 1/328}}$-time max-flow algorithm of $[12]$

to obtain $\bigO{mn^{1-\Omega(1)}}$-time algorithms for all problems in <Ref>.

Related Work.
The directed (edge) mincut problem has been studied over several decades. Early work focused on unweighted graphs [6, 27] eventually resulting in an $O(mn)$-time algorithm due to Mansour and Schieber [22]. This was matched (up to log factors) in weighted graphs by Hao and Orlin [16], whose result we improve in this paper. For unweighted graphs (and graphs with small integer weights), the current record is a recent $\tO(n^2)$-time algorithm due to Chekuri and Quanrud [3]. A similar story has unfolded for directed vertex mincuts. Early work again focused on unweighted graphs [25, 6, 4, 10] until the work of Henzinger, Rao, and Gabow [17] who obtained an $\tO(mn)$-time algorithm for weighted graphs. The current best for directed vertex mincut in unweighted graphs is an $\tO(m n^{11/12+o(1)})$-time algorithm due to Li et al. [20]. Faster algorithms are known when the mincut size is small and for $(1+\epsilon)$-approximations in unweighted digraphs [24, 8, 3].

§.§ Our Techniques

Our results are obtained by solving the $s$-mincut problem. Let us consider the edge-weighted case. Gabow [9] obtained a running time of $\tO(m\lambda)$ for this problem (assuming integer weights), where $\lambda$ is the size of an $s$-mincut. He did so via arborescense packing: Define an $s$-arborescense to be any spanning tree rooted at $s$ with edges pointing toward the leaves.

In $\tO(m\lambda)$ time, Gabow's algorithm computes $\lambda$ $s$-arborescenses such that an edge $e$ of weight $w(e)$ is contained in at most $w(e)$ arborescenses (this is called arborescense packing).[Gabow actually constructs a directionless spanning tree packing, which is a relaxation of an arborescence packing, but we ignore this technical detail here since it is not relevant to our eventual algorithm.]

Gabow's algorithm is at least as fast as that of Hao and Orlin for unweighted simple graphs (since $\lambda \le n-1$), but can be much worse for weighted (or multi) graphs. Nevertheless, Karger [18] gave an interesting approach to use arborescence packing for the mincut problem even with edge weights, but only in undirected graphs. Karger's algorithm had three main steps:

(a) sparsify the input graph $G$ to $H$ by random sampling of edges to reduce the mincut value in $H$ to $O(\log n)$ while guaranteeing that the mincut in $G$ is a $(1+\epsilon)$-approximate mincut in $H$,

(b) pack $O(\log n)$ $s$-arborescences[Since Karger's algorithm considered undirected graphs, the arborescences are simply spanning trees.]
in the sparsifier $H$, and

(c) find the minimum weight cut among those that have at most two edges in an arboresence using a dynamic program.

The last step is sufficient because the duality between cuts and arborescences ensures that an $s$-mincut, which is now a $(1+\epsilon)$-approximate mincut after sparsification, has at most two edges in at least one $s$-arborescence.[The duality implies that if the undirected mincut is $\lambda$, then we can pack $\lambda$ spanning trees where every edge appears in at most two arborescences.]

Karger implements all these steps in $\tO(m)$ time to obtain an $\tO(m)$-time mincut algorithm in undirected graphs.

Unfortunately, steps (a) and (c) in Karger's scheme are not valid in a directed graph.

To begin with, directed graphs do not admit sparsifiers similar to Karger's sparsifier: while Karger's sparsifier  approximately preserves all cuts in an undirected graph (after some scaling), it is well known that a sparsifier with a similar property does not exist in directed graphs (see, e.g., [1]).

This is mainly because we cannot bound the number of mincuts and approximate mincuts in directed graphs while we can do so in undirected graphs.

Partial sparsification.
Since it is impossible for a sparsifier to preserve all cuts in directed graphs, it is natural to try to preserve a partial subset of cuts.

Suppose we were guaranteed that the $s$-mincut $(S, V\setminus S)$ (recall that $s\in S$) is unbalanced in the sense that $|V\setminus S| \leq k$ for some parameter $k$ that we will fix later. Let us randomly
sample edges to scale down the value of the mincut to $\tO(k)$. In an undirected graph, as long as $k = \Omega(\log n)$, all the cuts would converge to their expected values. This is not true in digraphs, but crucially, all the unbalanced cuts converge to their expected values since there are only $n^{\tO(k)}$ of them.
However, it is possible that some balanced cut is (misleadingly) the new mincut of the sampled graph, having been scaled down disproportionately by the random sampling. So, we overlay this sampled graph with a star rooted at $s$, and show that this sufficiently increases the values of all balanced cuts, while only distorting the unbalanced cuts slightly. After this overlay, we can claim that we now have a digraph where $(S, V\setminus S)$ is a $(1+\epsilon)$-approximate mincut. We use one additional idea here. We show that in the sparsifier, every vertex in $V\setminus S$ has only $\apxO{k}$ incoming edges (note that each edge can be weighted)—$\apxO{k}$ edges across the cut from $S$ and $\le k$ edges from within $V\setminus S$. By contracting all vertices with unweighted in-degree $> \apxO{k} $ into $s$, we reduce the number of edges in the digraph to $\apxO{nk}$.

But, what if our premise that the $s$-mincut is unbalanced does not hold? This case is actually simple. We use a uniform random sample of $\tO(\frac{n}{k})$ vertices, and find $\root-\sink$ mincuts for all vertices $\sink$ from the sample, using $\tO(\frac{n}{k})$ maxflow calls. It is easy to see that whp, the sample hits $V\setminus S$, and hence, the minimum weighted cut among these $s-t$ mincuts will reveal the $s$-mincut of the graph.

Let us, therefore, return to the case where the $s$-mincut is unbalanced. Recall that we have already sparsified the graph to one that has only $\tO(nk)$ edges, and where the mincut has weight $\tO(k)$. The next step is to create a maximum packing of edge-disjoint $s$-arborescences. Because the graph is weighted, instead of using Gabow's algorithm described above, we create a (fractional) packing using a multiplicative weights update procedure (e.g., [30]). By duality,[By duality, we have that if the directed mincut is $\lambda$, then we can pack $\lambda$ arborescenses where each edge appears in at most one arborescense. Note that this is different from the case of undirected graphs where each edge appears in at most two arborescences.]

these arborescences have the following property: if we sample $O(\log n)$ random $s$-arborescences, then whp there will be at least one arborescence $T$ such that there is exactly one edge in $T$ that goes from $S$ to $V\setminus S$.

In this case, we say that the cut $(S, V\setminus S)$ $1$-respects the arborescence $T$.

Our 1-respecting cut algorithm.
Our final task, therefore, is the following: given an arborescence, find the minimum weight cut in the original graph among all those that $1$-respect the arborescence $T$. At first sight, this may look similar to part (c) of Karger's algorithm which can be solved by a dynamic program or other techniques (e.g. [21, 13, 14, 19]).

However, these techniques

relied on the fact that if the $s$-mincut $(S, V\setminus S)$ has a single edge $e$ in $T$, then
$S$ and $V\setminus S$ would be contiguous in an $s$-arborescence $T$ (i.e. removing $e$ from $T$ gives $S$ and $V\setminus S$ as the two connected components).

This is not true for a directed graph: While an $s$-arborescence will contain exactly one edge from $S$ to $V\setminus S$, it could contain an arbitrary number of edges in the opposite direction from $V\setminus S$ to $S$, thereby only guaranteeing the contiguity of $V\setminus S$ but not $S$.

One of the main contributions of this paper
is to provide an algorithm to solve the above problem using $O(\log n)$ maxflow computations. The main idea is to use a centroid-based recursive decomposition of the arborescence, where in each step, we use a set of maxflow calls that can be amortized on the original graph. The minimum cut returned by all these maxflow calls is eventually returned as the $s$-mincut of the graph.

Approximation Algorithms.
The ideas above also lead to a quadratic time approximation algorithm for edge mincuts. At a high level, if we execute each $(s,t)$-max flow in the sparsifier instead of in the input graph (both in the unbalanced and balanced settings, with care), then we obtain a $\tO(n^2/\eps^2)$ time $\epsmore$-approximation algorithm instead.

A similar approach can be taken for approximate vertex mincuts. Our partial sparsification technique reduces the graph to $\tO(nk/\epsilon^{2})$ edges while maintaining the vertex $s$-mincut (with some additional adjustments for vertex mincuts). For large $k$, we similarly run $(s,t)$-max flow between $\tO(n/k)$ pairs of vertices on the sparsifier. For small $k$, we design a new local cut algorithm from $\tO(n/k)$ seeds each of which takes $\tO(k^{3}/\epsilon^{2})$ time.
This local algorithm is inspired by local algorithms for unweighted graphs [8], and speeds up the running time by a factor of $k$ by leveraging the structure of our sparsifiers (beyond sparsity). We finally obtain $\tO(n^{2}/\epsilon^{2})$ running time by balancing the two cases and calling the max flow algorithm by [28].

A similar approach (at a high level) can be taken for approximate vertex connectivity. Again we focus on the rooted version of the problem with a fixed root $\root$. Suppose the sink component $\optSink$ of the minimum rooted cut has $k$ vertices. The first insight, similar to edge connectivity, is that one can reduce the graph to $\tO(n k / \eps^2)$ edges while maintaining the minimum rooted cut. Some technical adjustments are necessary since were are preserving vertex connectivity rather than edge connectivity, but at a high level we are still randomly sampling to preserve all $\root$-cuts induced by (roughly) $k$ or fewer vertices, while adding extra edges and vertices to force all cuts induced by much more than $k$ vertices to be large. Now, a random sample of $\apxO{n/k}$ vertices will include a vertex from $\optSink$ with high probability. Running $(\root,t)$-maximum flow for each sampled vertex $t$ in the sparsifier returns an $\epsmore$-approximate minimum vertex cut in the input graph. For $F(m,n) = \apxO{m + n^{1.5}}$, this gives a running time of

(n/k) F(nk/^2,n) = n^2 / ^2 + n^2.5 / k.

In particular this is $\apxO{n^2 / \eps^2}$ for $k \geq \sqrt{n}$, but not for $k = o(\sqrt{n})$. For this regime of smaller $k$, we design a new local $(s,t)$-flow algorithm which runs in $\apxO{k^3 / \eps^2}$ time per choice of $t$ in the sparsifier. We note that this running time holds specifically for the graph produced by the sparsification step, leveraging structure beyond simply reducing the number of edges. This leads to an $\apxO{n k^2 / \eps^2} \leq \apxO{n^2 / \eps^2}$ running time for $k \leq \sqrt{n}$, as desired.

To summarize, our algorithms distinguish between balanced and unbalanced mincuts, solving the former using maxflows on randomly sampled terminals. For unbalanced mincuts, we follow a two-step template. In the first step, we employ partial sparsification to preserve the values of unbalanced cuts approximately, while suppressing balanced cuts using an overlay. In the second step, we design algorithms to find the (edge/vertex) mincut among unbalanced cuts. For edge mincut, the sparsifier allows one to quickly obtain an arborescence that 1-respects the directed mincut. From this arboresence, we obtain the exact minimum cut in $O(\log n)$ max flows via a centroid-based recursive decomposition. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

To summarize, our main insights are to use sparsifiers with additional overlays and contractions for the unbalanced case, and to find the mincut that 1-respects an arborescence via maxlow and centroid-based recursive decomposition.

Overall, we run the algorithms for both the balanced and unbalanced cases, and return the minimum cut returned by either algorithm. For the balanced case, we need $\tO(\frac{n}{k})$ maxflows. For the unbalanced case, we need $\tO(1)$ maxflows in a graph containing $O(nk)$ edges. All other steps run in $\tO(m)$ time. Balancing these gives $k = \max(m^{1/3}, \sqrt{n})$, thereby resulting in <Ref>.

Summary (new).Here I have tried to extend the summary to capture both the edge and vertex connectivity algorithms.  At a high level, both the edge connectivity and vertex connectivity algorithms leverage the insight that when the minimum cuts are unbalanced, one can combine random sampling with contractions and other graph modifications to produce a smaller sparsifierq that approximately preserves the minimum cut. The sparsifier for edge connectivity allows one to quickly obtain an arborescence that 1-respects the minimum directed cut, from which the exact minimum cut can be obtained in $O(\log n)$ max flows via the new centroid-based recursive decomposition. Meanwhile, the sparsifier for vertex connectivity permits a substantially faster local algorithm for vertex cuts.  In the opposite regime, where the minimum cut is balanced,  the minimum cut can instead be obtained very quickly by randomly sampling a source and sink from opposite sides of the minimum cut, and running $(s,t)$-max flow.  (The quadratic time approximation algorithms also apply the sparsifiers in the balanced setting before running max flow.) This combination of approaches – exploiting a tradeoff between better sparsifiers for more unbalanced minimum cuts with fewer source-sink samples for more balanced minimum cuts – leads to the improved running time for directed minimum cut.

I suggest dropping the following paragraph, relying on a somewhat similar discussion in Section 2. Somewhere up above I placed a sentence saying: "If instead we execute each $(s,t)$-max flow in appropriately sparsified graphs (both in the unbalanced and balanced settings, with care), then we obtain am $\tO(n^2/\eps^2)$ time algorithm instead."

Did we hide $\log U$ anywhere (except when we use <cit.>)?

Related Work.
The mincut problem has been studied in directed graphs over several decades. Early work focused on unweighted graphs, starting with the work of Even and Tarjan in 1975 [6], followed by improvements by Schnorr [27], and eventually resulting in an $O(n\cdot \min(m, \lambda^2 n))$-time algorithm due to Mansour and Schieber [22]. This was matched in weighted graphs by Hao and Orlin [16], whose result we improve in this paper.

Note that the $\tO(mn)$ bound was recently improved in unweighted directed graphs for both edge and vertex mincut problems. Chekuri and Quanrud  [3] give a $\tO(n^2)$-time algorithm for finding directed edge mincuts.[In fact, the algorithm works on graphs with integer capacities between $1$ and $U$ and takes $\tO(n^2 U)$ time] A key idea in this work is a deterministic rooted sparsification technique that inspires some of the ideas in this work.  For directed vertex mincuts, there are algorithms with $\tO(m n^{11/12+o(1)})$ time [20] and even  faster algorithms when the mincut size is small and/or when $(1+\epsilon)$-approximation is allowed [24, 8, 3]. The techniques from these recent developments seem to heavily rely on the fact that the input graph is unweighted.

TO DO: The below are moved from other parts of the paper and needs to be cleaned up. We might miss some papers too.

To do: Compare our technique with Kent-Chandra?

Directed mincut.
For unweighted graphs, Even and Tarjan [6] gave an algorithm for this problem that runs in $O(mn \cdot\min(\sqrt{m}, n^{2/3}))$ time. Schnorr [27] improved this bound for certain graphs to $O(mn\lambda)$, where $\lambda$ is the value of the directed mincut. This was further improved by Mansour and Schieber [22] to $O(n\cdot \min(m, \lambda^2 n))$ almost a decade after Schnorr's work.  Finally, the Hao-Orlin result matched Mansour-Schieber's bound of $O(mn)$ up to logarithmic factors for the more general case of weighted digraphs. The recent work of [3] mentioned above gives a $\tO(n^2 U)$ randomized algorithm for directed graphs with integer capacities between $1$ and $U$. A key idea in this work is a deterministic rooted sparsification technique that inspires some of the ideas in this work. [3] also exploits tradeoffs between balanced and unbalanced minimum cuts.

Below is Kent's stuff from Appendix

Directed vertex cut.
Directed vertex cut likewise has a long history of algorithmic research, and
many of these running times are parametrized by the weight of the
vertex cut
As mentioned above, the analogue of the Hao-Orlin result for vertex connectivity the randomized $O(m n \log {n})$ time algorithm of Henzinger, Rao, and Gabow [17] that remains the fastest algorithm in weighted and directed graphs. [17] is based on similar techniques as [16], extending the push-relabel algorithm to find all minimum rooted cut values. There has also been several recent algorithms for vertex connectivity in unweighted algorithms, obtaining running times of $\tO(m \kappa^2)$ and $\tO(n \kappa^2)$ [8], $\tO(\kappa m^{2/3} n)$ and $\tO(\kappa m^{4/3})$, $\tO(m n^{11/12+o(1)})$ [20], and $\tO(n^2 \kappa)$ [3], where $\kappa$ denotes the size of the vertex connectivity. There are also $(1+\epsilon)$-approximations running in $\tO(m \kappa / \epsilon)$ [8], $\tO(n^{\omega} / \epsilon^2 + m \min\{\kappa, \sqrt{n}\})$ <cit.> and $\tO(n^2 / \epsilon)$ [3] in unweighted graphs. These algorithms highlight several new techniques including local connectivity algorithms [8], isolating cuts [20], and rooted sparsification [3].

To overcome these challenges, we adopt several ingredients that we outline below:

* We consider two possibilities: either the mincut has $\tOmega(k)$ vertices on the smaller side or fewer (let us call these balanced and unbalanced cuts respectively). If the mincut is a balanced cut, we use two random samples of $\tO(\frac{n}{k})$ and $\tO(1)$ vertices each, and find $s-t$ mincuts for all pairs of vertices from the two samples. It is easy to see that whp, the two samples would respectively hit the smaller and larger sides of the mincut, and hence, one of these $s-t$ mincuts will reveal the overall mincut of the graph.

* The main task, then, is to find the mincut when it is unbalanced. In this case, we use a sequence of steps. The first step is to use cut sparsification of the graph by random sampling of edges. This scales down the size of the mincut, but unlike in an undirected graph, all the cuts of a digraph do not necessarily converge to their expected values in the sample. However, crucially, the mincut can be scaled to $\tO(k)$ while ensuring that all the unbalanced cuts converge to their expected values.

* Since only the unbalanced cuts converge to their expected values, it is possible that some balanced cut is the new mincut of the sampled graph, having been scaled down disproportionately by the random sampling. Our next step is to overlay this sampled graph with an star,
which increases all balanced $s$-cuts to be  sufficiently large, while the unbalanced cuts are only distorted by a small multiplicative factor.

* In the sparsifier, all vertices in the sink side of a potential minimum $s$-cut will have unweighted in-degree at most $O(k)$. Therefore, when $m>nk$, we can contract all vertices with large unweighted in-degree to $s$, in order to decrease the edge size to $O(nk)$.

* At this point, we have obtained a graph where the original mincut (which was unbalanced) is a near-mincut of the new graph. Next, we create a (fractional) packing of edge-disjoint arborescences[An arborescence is a spanning tree in a directed graph where all the edges are directed away from the root.] in this graph using a multiplicative weights update framework (e.g., [30]). By duality, these arborescenes have the following property: if we sample $O(\log n)$ random arborescences from this packing, then there will be at least one arborescence whp such that the original mincut $1$-respects the arborescence. (A cut $1$-respects an arborescence if the latter contains just one edge from the cut.)

* Thus, our task reduces to the following: given an arborescence, find the minimum weight cut in the original graph among all those that $1$-respect the arborescence. Our final technical contribution is to give an algorithm that solves this problem using $O(\log n)$ maxflow computations. For this purpose, we use a centroid-based recursive decomposition of the arborescence, where in each step, we use a set of maxflow calls that can be amortized on the original graph. The minimum cut returned by all these maxflow calls is eventually returned as the mincut of the graph.

We note that unlike both the Hao-Orlin algorithm and Gabow's algorithm that are both deterministic algorithms, our algorithm is randomized (Monte Carlo) and might yield the wrong answer with a small (inverse polynomial) probability. Derandomizing our algorithm, or matching our running time bound using a different deterministic algorithm, remains an interesting open problem.

Previous Work.more refs from Kent's manuscript
The mincut problem has been studied in directed graphs over several decades. For unweighted graphs, Even and Tarjan [6] gave an algorithm for this problem that runs in $O(mn \cdot\min(\sqrt{m}, n^{2/3}))$ time. This was improved by Schnorr [27] improved by this bound for certain graphs to $O(mn\lambda)$, where $\lambda$ is the value of the directed mincut. This was further improved by Mansour and Schieber [22] to $O(n\cdot \min(m, \lambda^2 n))$ after almost a decade of Schnorr's work. Mansour and Schieber's bound of $O(mn)$ was matched up to logarithmic factors for the more general case of weighted digraphs by Hao and Orlin [16]. Finally, Gabow [9] gave an algorithm that runs in $\tO(m\lambda)$ which further refines this bound for graphs with small $\lambda$. These remained the fastest directed mincut algorithms for almost 30 years before our work.

Concurrent Work.
Two recent results on algorithms for finding mincuts in directed graphs were obtained concurrently and independently of our work. First, Chekuri and Quanrud <cit.>  showed an exact algorithm with running time $\tO(n^2 U)$ if edge weights are integers between $1$ and $U$.
Second, Quanrud [26] has obtained an $(1+\epsilon)$-approximate algorithm that runs in $\tilde{O}(n^2/\epsilon^2)$ time.[Quanrud can also obtain $o(mn)$-time algorithms using the currently fastest maxflow algorithm on sparse graphs by Gao, Liu, and Peng <cit.>. We can also obtain the same time but for exact mincuts.]
Both papers also extend their ideas to obtain approximation results for other problems as well, such as the vertex mincut problem.

§ MINIMUM CUT ALGORITHMS IN EDGE-WEIGHTED DIRECTED GRAPHS

Given a directed graph $G = (V, E)$ with non-negative edge weights $w$ and a fixed root vertex $s$, we consider the problem of finding an $s$-mincut.
An $s$-arborescence is a directed spanning tree rooted at $s$ such that all edges are directed away from $s$.
For simplicity, we assume that all edge weights $w$ are integers and are polynomially bounded.  We denote $\overline{U}=V\setminus U$.  Let $\outcut{U}$ be the set of edges from $U$ to $\overline{U}$, $\incut{U}$ be the set of edges from $\overline{U}$ to $U$, and let $\outcutsize(U)$ and $\incutsize(U)$ be the weight of the cut, i.e., $\outcutsize(U)=\sum_{e\in \outcut{U}}w(e), \incutsize{U}=\sum_{e\in \incut{U}}w(e)$.  Our goal is to compute the minimum cut $(\optSource, \optSink)$ where $\root \in \optSource = \arg\min_{s\in U \subset V} \outcutsize{U}$ and $\optSink = \overline{\optSource}$.

Let $F(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 $F(m, n) = \tO(m + n^{3/2})$ [28]. 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 $F(m, n)$.

There is a Monte Carlo algorithm that finds a minimum $s$-cut whp in $\tO(\min\{mk, nk^2\}+F(m,n)\frac{n}{k})$ time, where $k$ is a parameter and $F(m,n)$ is the time complexity of $s$-$t$ maximum flow.

This section is devoted to prove <Ref>.  If we set $k=m^{1/3}+n^{1/2}$ and use the $\tO(m+n^{3/2})$ max-flow algorithm, the time complexity becomes $\tO(nm^{2/3}+n^2)$, which establishes <Ref>.  If we assume an hypothetical $\tO(m)$-time max-flow algorithm, then our result becomes $\tO(\min\{nm^{2/3},mn^{1/2}\})$ for $k=\min\{m^{1/3},n^{1/2}\}$.

We obtain <Ref> via a new $s$-mincut algorithm. The algorithm considers the following two cases, computing a $s$-cut for each case and returning the minimum as its final output. The cases are split on $|\optSink|$ by a threshold $k>0$.

* The first case aims to compute the correct mincut in the event that $|{\optSink}| > k$. In this case, if we randomly sample $\sink \in V$, then with probability at least $1/k$, $\sink \in \optSink$. Then $\optSink$ can be obtained via the maxflow from $s$ to $t$. Repeating the sampling $O(\frac{n}{k}\log n)$ times, we obtain the minimum $\root$-cut whp. The total running time for this case is $O(F(m,n)\frac{n}{k}\log n)$.
and is formalized in Lemma <ref> below:

Let $k \in \mathbb{N}$ be a given parameter.  If $|\optSink| > k$, then whp a mincut can be calculated in time $O(F(m,n) \cdot k \cdot \log n)$.

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^*| \le |\overline{S^*}|$, and let $\eta=\frac{|S^*|}{n}>\frac{r}{n}$.  With probability at least $1-2(1-\eta)^k\ge 1-2e^{-k\eta}\ge 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.

* The second case is for the the event that $|{\optSink}| \le k$.
Let $\lambda$ denote the value of the minimum rooted cut. By enumerating $O(\log n)$ powers of $2$, we can obtain an estimate $\varec$ such that $\ec \leq \varec \leq 2\ec$. For each value of $\varec$,  we apply <Ref> to sparsify the graph in the following manner. First, <Ref> returns a set of vertices $\sparseV \subseteq V$ such that $\root \in \sparseV$ and $\optSink \subseteq \sparseV$ whp. In particular, one can safely contract any vertex $v \in V \setminus \sparseV$ into $\root$ without affecting the minimum $\root$-cut. We contract $G$ accordingly and, overloading notation, let $G$ denote the contracted graph with vertex set $V_0$ henceforth. Second, <Ref> returns a graph $\sparseG = (\sparseV, \sparseE)$ in which $\optSink$ still induces an $\epsmore$-approximate $s$-mincut, but the weight of the cut is now reduced to $\bigO{k \log{n}}$. We note that $\sparseG$ is not necessarily a subgraph of $G$. We then invoke  <Ref> from <Ref> to fractionally pack an approximately maximum amount of $O(k \log n)$ $s$-arboresences in $\sparseG$ in $\apxO{m+\min{mk, nk^2}}$ time. In a random sample of $\bigO{\log n}$ $s$-arboresences from this packing, one of them will $1$-respect the $s$-mincut in $G$ (for appropriate $\varec$) whp:

A directed $s$-cut $(S, V \setminus S)$ $k$-respects an $s$-arborescence if there are at most $k$ edges in the arborescence from $S$ to $V \setminus S$.

Finally, for each of the $O(\log n)$ $s$-arborescences, the algorithm computes the minimum $\root$-cut that $1$-respects each arborescence. This algorithm is described in Algorithm <ref> and proved in <Ref> from <Ref>. It runs in $O((F(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(\min\{mk, nk^2\} + F(m,n)\frac{n}{k})$, which establishes <Ref>.

Fast approximations.
The exact algorithm described above can be modified to produce a
randomized $\apxO{n^2/\eps^2}$-time approximation algorithm that
computes a $\epsmore$-approximate minimum $\root$-cut (hence also the
global cut).  With logarithmic overhead, we can obtain a parameter
$k$ such that $k / 2 \leq \sizeof{\optSink} \leq k$, where
$\incut{\optSink}$ is the minimum  $\root$-cut. We then follow the
same steps as in the exact algorithm, except whenever we compute the
max-flow, we compute it in the sparsifier produced by
<Ref> instead. Since the sparsifier has at
most $\apxO{nk / \eps^2}$ edges, we obtain a running time of the

minnk^2 / ^2 + F(nk / ^2,n) (n/k).

For $F(m,n) = \apxO{m + n^{1.5}}$, this gives a running time of $\apxO{n^2 / \eps^2}$.

For $\eps \in (0,1)$, an $\epsmore$-approximate minimum $s$-cut  (hence global minimum cut) can be computed in $\tO(n^2 / \eps^2)$ time whp.

We remark that $\apxO{n^2 / \eps^2}$ can also be obtained by using a local connectivity algorithm similar to the approach for vertex mincuts in apx-vc, instead of via an arboresence packing. See [26] for details.

Organization of the rest of this section.
The following subsections present each step of the algorithm described above. First, we establish the partial sparsification subroutine in <Ref>. Next, in <Ref>, we obtain an arborescence packing from which sampling yields an arborescence that is $1$-respected by the mincut. Finally, in <Ref>, we describe the algorithm to retrieve the mincut among those that $1$-respect a given arborescence.

§.§ Partial Sparsification

§.§ Finding a 1-respecting Arborescence

§.§ Mincut Given 1-respecting Arborescence

This section aims to reduce mincut value to $\tO(k)$ and
edge size to $\min\{m,O(nk\log{n}/\epsilon^2\})$ while keeping $\outcut{\optSource}$ a
$(1+\epsilon)$-approximate $s$-mincut for a constant $\epsilon > 0$ that
we will fix later.  Our algorithm in this stage has three
steps. First, we use random sampling to discretize and scale down the
expected value of all cuts such that the expected value of the mincut
$\outcutsize(\optSource)$ becomes $\tO(k)$. We also claim that $\outcut(\optSource)$
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
$\outcut(\optSource)$ should be an approximate mincut in this new
graph. This is where we need our second step, where we overlay a star
on the sampled graph to raise the values of all balanced $s$-cuts
above the expected value of $\outcut(\optSource)$ while only increasing the
value of $\outcut(\optSource)$ by a small factor. The third step leverages
the fact that, after scaling, the minimum edge weight is $1$, and the
minimum cut is $\bigO{k \log{n} / \eps^2}$. It follows that any vertex
with in-degree at least a constant factor greater than
$k \log{n} / \eps^2$ cannot be in the sink component, and can be
safely contracted into the root without affecting the $s$-mincut.

The first two steps described above are implemented in the next lemma,
whose proof appears in <Ref>.

apx-rec-skeleton Let $G = (V,E)$ be a directed graph
with positive edge weights. Let $\root \in V$ be a fixed root
vertex. Let $\eps \in (0,1)$, let $\ec > 0$, and let
$k \in \naturalnumbers$ be given parameters. Suppose there is an
$\root$-mincut of the form $\incut{\optSink}$, where $\root \not\in T^*$,
$\ec/2 \leq \incutsize{\optSink}{G} \leq 2 \ec$ and
$\sizeof{\optSink} \leq k$.  In randomized nearly linear time, one can
compute a randomized directed and reweighted subgraph
$\sparseG = (V, \sparseE)$, where $\sparseV \subseteq V$ and
$\root \in \sparseV$ with the following properties.

*  $\sparseG$ has integral edge weights and the minimum $\root$-cut has weight at most
$\bigO{k \log{n} / \eps^2}$.

*  $\incut{\optSink}{G_0}$ is a
$\epsmore$-approximate minimum $\root$-cut in $G_0$.

*  Every $\alpha$-approximate
minimum $\root$-cut in $G_0$ induces an $\epsmore \alpha$-approximate
minimum $\root$-cut in $G$.

The preceding lemma importantly allows us to reduce the weight of the minimum cut to roughly $k$, where $k$ is the number of the vertices in the sink component. However it has not actually reduced the size in the graph, in terms of the number of edges. This is accomplished by our third step, which we formalize in  the following lemma that reduces the number of edges to $\tO(nk)$.

apx-rec-sparsification Let $G = (V,E)$ be a directed
graph with positive edge weights.  Let $\root \in V$ be a fixed root
vertex. Let $\eps \in (0,1)$, $\ec > 0$, and
$k \in \naturalnumbers$ be given parameters.  Suppose there is a
minimum $\root$-cut is of the form $\incut{\optSink}$, where
$\ec/2 \leq \incutsize{\optSink}{G} \leq 2 \ec$ and $\sizeof{\optSink} \leq k$.

In randomized nearly linear time, one can compute a randomized directed and edge-weighted graph $\sparseG = (\sparseV, \sparseE)$, where $\sparseV \subseteq V$ and $\root \in \sparseV$.

* $\sparseG$ has integral edge weights and the $s$-mincut in $\sparseG$ has weight at most $\bigO{k \log{n} / \eps^2}$.

* $\sparseG$ has at most
$\sizeof{\sparseE} = \min{m, \bigO{nk \log{n} / \eps^2}}$ edges.

* $\sparseG$ is a subgraph of the graph obtained by contracting
$V \setminus V_0$ into $\root$ in $G$.

* We have $\optSink \subseteq V_0$, and $\incut{\optSink}{G_0}$
is an $\epsmore$-approximate minimum $\root$-cut in $G_0$.

* Every $\epsmore$-approximate minimum $\root$-cut in $G_0$ induces
an $\epsmore^2$-approximate minimum $\root$-cut in $G$.

Consider the reweighted subgraph produced by
apx-rec-skeleton, which we denote by $G_1 = (V, E_1)$. We
claim that every vertex $v \in \optSink$ has unweighted
in-degree at most $\bigO{k \log{n} / \eps^2}$. Indeed, at most $k-1$
of these edges are from other vertices in $T$, and the remaining
edges must be in $\incut{\optSink}{G_1}$. But
$\incut{\optSink}{G_1}$ has at most
$\incutsize{\optSink}{G_1} = \bigO{k \log{n} / \eps^2}$ edges by
properties <ref> and
<ref> of apx-rec-skeleton.

Let $G_0 = (V_0, E_0)$ be the graph obtained from $G_1$ by
contracting all vertices with unweighted in-degree
$\geq c k \log{n} / \eps^2$ for a sufficiently large constant $c$
that excludes all vertices in $\optSink$.  It is easy to see that
$G_0$ satisfies the claimed properties, particularly as contractions
into $\root$ do not decrease the $s$-mincuts, and
$\incut{\optSink}{G_0}$ is preserved exactly as in $G_1$.

I'm pretty sure that $\eps^2$-dependency can also be obtained
via arboresences, but I am leaving this here for the time being in
case any parts of the writing might be helpful. In this section, we
design and analyze an $\apxO{n^2 / \eps^2}$-time approximation
algorithm for the minimum weight rooted edge cut.  Here the point of
emphasis is the improved dependency on $\eps$.  We present the
algorithm as three main steps. Each of the steps are parameterized by
values $\lambda > 0$ and $k \in \naturalnumbers$ that, in principle,
are meant to be constant factor estimates for the weight of the
minimum rooted cut and the number of vertices in the sink component of
the minimum rooted cut, respectively. The first step is the
sparsification result (apx-rec-sparsification) that
(assuming $\lambda$ and $k$ are accurate) reduces the problem to a
rooted graph with roughly $nk$ edges and rooted connectivity roughly
$k$ in addition to a few other helpful properties. This sparsification
procedure is used by both of the remaining two steps.  The second
step, preferable for small $k$, approximates the minimum rooted cut in
roughly $nk^2$ time, and is based on a new deterministic local cut
algorithm that makes essential use of some of the specific properties
of the sparsification lemma. The third step, preferable for large $k$,
approximates the minimum rooted cut in roughly $n^2 + n^{2.5}/k$ time,
via random sampling and $(s,t)$-flow in the sparsified
graph. Balancing terms leads to the claimed running time.

Rooted connectivity for large sink components.
The second subroutine we present is better suited for cases where the
sink component is very large.

apx-rec-big-sink Let $G = (V,E)$ be a directed graph
with positive edge weights.  Let $r \in V$ be a fixed root.  Let
$\eps, k, \ec > 0$ be given parameters with $\eps$ sufficiently
small.  Let $\optec$ be the minimum weight of all $r$-cuts where the
sink component has between $k/2$ and $k$ vertices.  Then there is a
randomized $\apxO{n^2 / \eps^2 + n^{2.5} / k}$ time algorithm that
has the following guarantee. If $\optec \leq \ec$, then with
probability, the algorithm returns an $r$-cut of capacity at most
$\optec + \eps \ec$.

We assume the graph $\sparseG = (\sparseV, \sparseE)$ produced by
apx-rec-sparsification with parameters $k$, $\ec$, and
$c \eps$ for a sufficiently small constant $c > 0$.  Let
$\optSink \subseteq V - r$ be the sink component of the minimum
$r$-cut subject to $k/2 \leq \sizeof{\optSink} \leq k$, and suppose
the capacity of $\optSink$ is at most $\ec$.  We randomly sample
$\bigO{n \log{n} / k}$ sinks $t \in \sparseV$, and for each compute
the minimum $(r,t)$ cut. We output the minimum of these cuts.

If $\optec \leq \ec$, then apx-rec-sparsification asserts
that with high probability we have $\optSink \subseteq \sparseV$.
With high probability, some $t$ will be drawn from $\optSink$ and
the corresponding $(r,t)$-cut has capacity at most
$\epsmore \optec + \eps \lambda$.  We use
$\ectime{m}{n} = \apxO{m+n^{1.5}}$ <cit.>.  By
apx-rec-sparsification, we have
$m = \bigO{n k \log{n} / \eps^2}$.

Rooted and global edge connectivity.
Finally we combine the two approaches above for rooted connectivity –
apx-rec-small-sink for small components, and
apx-rec-big-sink for large components – in an overall
algorithm for rooted edge connectivity and establish
apx-ec. We restate apx-ec for the sake of
convenience.In the original manuscript, this was restated from
the introduction.

apx-ec Given a directed graph with polynomially
bounded weights, and $\eps \in (0,1)$, a $\epsmore$-approximate
minimum rooted or global edge cut can be computed with high
probability in $\apxO{n^2 / \eps^2}$ randomized time.

We focus on rooted connectivity from which global connectivity
follows immediately.  As the weights are polynomially bounded, we
can guess the rooted connectivity $\lambda$ and the number of
vertices $k$ in the sink component of the minimum rooted cut up to a
multiplicative factor of 2 with polylogarithmic overhead. For each
choice of $k$, we apply the faster of apx-rec-small-sink
and apx-rec-big-sink.  We balance the

n k^2 / ^4

running time of apx-rec-small-sink with the

n^2 / ^2 + n^2.5 / k

running time of apx-rec-big-sink.  For
$k = \sqrt{n} \eps^{4/3}$, we obtain the claimed running time.

§ MINIMUM CUT ALGORITHMS IN VERTEX-WEIGHTED DIRECTED GRAPHS

In this section we present the approximation algorithm for the minimum
rooted and global vertex cut. Similar to <Ref>, the
main focus is on rooted cuts, and the algorithm is presented in three
main parts. All three parts are parameterized by values $\vc > 0$ and
$k \in \naturalnumbers$ that, in principle, are meant to be constant
factor estimates for the weight and the number of
vertices in the sink component of the minimum rooted vertex cut. The
first part, in <Ref>, presents the
sparsification lemma that reduces the number of edges to roughly $nk$
and the rooted mincut to roughly $k$ in a graph with integer
weights. This sparsifier is used in the remaining two parts. The
second part, in <Ref>, gives a roughly $nk^2$ time
approximation algorithm for the minimum rooted cut via a new local
flow algorithm. The third part, in <Ref>, gives a roughly
$n^2 + n^{2.5} / k$ time approximation algorithm via sampling and
$(\root,\sink)$-flow (as with minimum edge cuts before). Finally, in
<Ref>, we balance terms to obtain the claimed
running time for rooted cut. The rooted vertex mincut
algorithm then leads to a global vertex mincut algorithm via an
argument due to [17] (with some modifications).

§.§ Partial Sparsification

The first part is a sparsification lemma that preserves rooted vertex
cuts where the number of vertices in the sink component is below some
given parameter.  It is similar in spirit to
<Ref>, but with some necessary changes as we are
now preserving the vertex mincut rather than edge
mincut.   We give a brief overview of the algorithm, highlighting in particular the differences from the partial edge cut sparsifier. The proof and algorithmic details are deferred to <Ref>.

At a high level, the following sparsifier for vertex cuts randomly samples the vertex weights so that the weights are integral, and the weight of the minimum vertex cut becomes $\bigO{k \log{n} / \eps^2}$. Similar to the partial edge sparsifier, this rounding is calibrated to preserve $\root$-cuts with (roughly) $k$ or fewer vertices in the sink components. To pad the weight of vertex $\root$-cuts with large sink components, we add an weighted auxiliary vertex on a short directed path between $\root$ and each vertex (as opposed to just adding an edge from $\root$, as we did for edge cuts). If a sampled weight of a vertex $v$ is $0$, we cannot simply drop the vertex from the graph (in the way we can drop weight $0$ edges) since the vertex may be in the sink component of the min $r$-cut. Instead we remove all outgoing edges from $v$.
Also, when we detect that a vertex $v$ cannot be in the sink component (by a similar counting argument as before), rather than contract $v$ into $\root$ (which may effect the min vertex $\root$-cut), we replace all of the incoming edges to $v$ with a single edge from $\root$. The culmination of these modifications is a similar net effect as for edge cuts: a graph with $\bigO{n k \log{n} / \eps^2}$ that preserves the sink component of the minimum vertex $\root$-cut.
That said, the following bounds are more detailed than the bounds for preserving the edge cut in <Ref>. These additional properties play a critical role in the customized local flow algorithms presented later.

In the following, let $\outneighbors{v}{G}$ denote
the set of out-neighbors of $v$ in the graph $G$. We omit $G$ and
simply write $\outneighbors{v}$ when $G$ can be inferred from the

apx-rvc-sparsification Let $G = (V,E)$ be a directed
graph with positive vertex weights.  Let $\root \in V$ be a fixed
vertex.  Let $k, \vc > 0$ be given parameters.  Let
$V' = V \setminus \parof{\setof{\root} \cup \outneighbors{\root}}$.
In randomized linear time, one can compute a randomized directed and
vertex-weighted graph $\sparseG = (\sparseV, \sparseE)$, and a
scaling factor $\tau > 0$, with the following properties.

*  $\root \in \sparseV$.

*  Let
$\sparseV' = \sparseV \setminus \parof{\setof{\root} \cup
\outneighbors{\root}{\sparseG}}$. We have $\sparseV' = V'$.

*  $\sparseG$ has integer vertex weights
between $0$ and
$\bigO{k \log{n} / \eps^2}$.

*  Every vertex $v \in \sparseV$ has at most
$\bigO{k \log{n} / \eps^2}$ incoming edges.

*  Every vertex $v$ with weight $0$ has no
outgoing edges.

*  With high probability, for all
$S \subseteq V'$, the weight of the vertex in-cut induced by $S$
in $\sparseG$ (up to scaling by $\tau$) is at least the minimum of
the $\epsless$ times the weight of the induced vertex in-cut in
$G$ or $c \vc$ (for any desired constant $c > 1$), and at most
$\epsmore$ times its weight in $G$ plus $\eps \vc \sizeof{S} / k$.

*  With high probability, for all
$S \subseteq V'$ such that $\sizeof{S} \leq k$ and the weight of
the induced vertex in-cut is $\leq \bigO{\vc}$, we have
$S \subseteq \sparseV'$. (That is, $S$ is still the sink component
of an $\root$-cut in $\sparseG$.)

In particular, if the minimum vertex $\root$-cut has weight
$\bigTheta{\vc}$, and the sink component of a minimum vertex $\root$-cut
has at most $k$ vertices, then with high probability $\sparseG$
preserves the minimum vertex $\root$-cut up to a
$\apxmore$-multiplicative factor.

As stated above, the proof is deferred to <Ref>.

§.§ Rooted vertex mincut for large sink components

The third and final part (before the overall algorithm) is an
approximation for the rooted vertex cut that is well-suited for large
sink components.

Let $G = (V,E)$ be a directed graph with positive vertex
weights. Let $\root \in V$ be a fixed root vertex. Let $\eps \in (0,1)$,
$\vc > 0$, and $k \in \naturalnumbers$ be given parameters. There is
a randomized algorithm that runs in

m + (n - ) n / ^2 + n^1.5 / k

time and has the following guarantee. If there is a vertex $\root$-cut
of capacity at most $\vc$ and where the sink component has at most
$k$ vertices, then with high probability, the algorithm returns a
vertex $(\root,t)$-cut of capacity at most $\epsmore \vc$.

Let $\optSink$ be the sink component of the minimum $\root$-cut subject
to $\sizeof{\optSink} \leq k$. We assume the capacity of the $\root$-cut
induced by $\optSink$ is at most $\vc$. (Otherwise the output is not
well-defined.) Let
$V' = V \setminus \parof{\setof{\root} \cup \outneighbors{\root}}$ and note
that $\sizeof{V'} < n - \outdegree{\root}$.

We apply apx-rvc-sparsification to produce the graph
$\sparseG$. apx-rvc-sparsification succeeds with high
probability and for the rest of the proof we assume it was
successful. (Otherwise the algorithm fails.)  We sample
$\bigO{ \parof{n - \outdegree{\root}} \log{n} / k}$ vertices
$t \in V'$. For each sampled $t$, we compute the minimum
$(\root,t)$-vertex cut in $\sparseG$. With high probability, some
$t$ will be drawn from the sink component of the true minimum
$\root$-cut, in which case the minimum $(\root,t)$-cut in $\sparseG$
gives an $\epsmore$-approximate $\root$-cut in $G$ (by
apx-rvc-sparsification).  We use the $\apxO{m + n^{1.5}}$
time vertex-capacitated flow algorithm [29]. By
apx-rvc-sparsification, we have
$m = \bigO{n k \log{n} / \eps^2}$. This gives the total running

§.§ Approximating the rooted and global vertex mincut

We now combine the two parameterized approximation algorithms for
rooted vertex mincut to give the following overall algorithm for
rooted vertex mincut. This establishes one part of
<ref> concerning approximate rooted vertex cuts.

apx-rvc Let $\eps \in (0,1)$, let $G = (V,E)$ be a
directed graph with polynomially bounded vertex weights, and let
$\root \in V$ be a fixed root. A $\epsmore$-approximate minimum vertex
$\root$-cut can be computed with high probability in
$\apxO{m + n (n - \outdegree{\root}) / \eps^2}$ randomized time.

The high-level approach is similar to <Ref> for edge
mincut – we are balancing two algorithms for rooted vertex
mincut, where one is better suited for small sink components,
the second is better suited for large sink components. Both leverage
the randomized sparsification lemma.  As before, with
polylogarithmic overhead, we can assume access to values $\vc$ and
$k$ that are within a factor 2 of the weight of the minimum $\root$-cut
and the number of vertices in the sink component of the minimum
$\root$-cut, respectively.  For a fixed choice of $k$ and $\vc$, we
run the faster of two randomized algorithms, both of which would
succeed with high probability when $k$ and $\vc$ are
(approximately) correct.  The first option, given by
apx-rvc-small-sink, runs in
$\apxO{(n - \outdegree{\root}) k^2 / \eps^3}$.  The second option, given
by apx-rvc-big-sink, runs in
$\apxO{n(n-\outdegree{\root}) / \eps^2 + n^{1.5} (n - \outdegree{\root}) /
k}$.  The overall running time is obtained by choosing $k$ to
balance the running times.  For $k = \eps \sqrt{n}$, we obtain the
claimed running time.

Next we use the algorithm for rooted vertex mincut to obtain an
algorithm for global vertex mincut and establish
apx-vc.  17 showed that running times of
the form $(n-\outdegree{\root}) T$ for rooted mincut from a root $\root$
imply a randomized $n T$ expected time algorithm for global vertex
mincut.  apx-rvc gives a
$\apxO{m + n (n-\outdegree{\root}) / \eps^2}$ running time, so some
modifications have to be made to address the additional $\apxO{m}$
additive factor.  This establishes the remaining part of <ref>.

apx-vc For all $\eps \in (0,1)$, a
$\epsmore$-approximate minimum weight global vertex cut in a
directed graph with polynomially bounded vertex weights can be
computed with high probability in $\apxO{n^2 / \eps^2}$ expected

Let $T = \apxO{n / \eps^2}$.  Let $w: V \to \preals$ denote the
vertex weights, and let $W = \sum_{v \in V} \weight{v}$ be the total
weight of the graph. Let $\vc$ denote the weight of the minimum
global vertex cut. The algorithm samples
$L = \bigO{W \log{n} / (W - \vc)}$ vertices $\root$ in proportion to
their weight, and – morally, but not actually – computes the
minimum $\root$-vertex cut for each sampled vertex $\root$ via
apx-rvc. It returns the smallest cut found.

For the sake of running time, we adjust the algorithm from
apx-rvc. Recall that for a fixed root $\root$, and for
each of a logarithmic number of values for $k$ and $\vc$, the
algorithm from apx-rvc applies
apx-rvc-sparsification which reduces the graph to having
$\apxO{n k / \eps^2}$ edges and rooted mincut $\apxO{k/\eps^2}$. For
fixed $k$ and $\vc$, rather than rerun
apx-rvc-sparsification entirely for each $\root$ we
sample, we execute most of it just once for all $\root$, and make
local modifications for each different root $\root$. Referring to
the algorithm given in the proof of
apx-rvc-sparsification, observe that the only step that
directly mentions $\root$ is step rvc-extra-vertices,
which adds auxiliary vertices between $\root$ and each other vertex
$v$. We move this step to the very end of the algorithm. (Here the
vertex weight of auxiliary vertices is scaled down appropriately.)
It is easy to see that the proof of
apx-rvc-sparsification still goes through (with minor
rearrangement in the argument). The advantage is that, over all $L$
roots $\root$, we now spend a total of $\bigO{m + n L}$ time, rather
than $\bigO{m L}$.  Thereafter, the rest of the rooted mincut
algorithm takes $\apxO{(n-\outdegree{\root}) T}$ per root
$\root$. Note that $\apxO{(n-\outdegree{\root}) T}$ dominates the
$\bigO{n}$ time required to complete the sparsification for each

Consider a single root $\root$ sampled from $V$ in proportion to its
weight. The expected running time to compute the minimum $\root$-cut is

\begin{align*}
\evof{\parof{n - \outdegree{\root}} T}
=                           %
n T - \frac{T}{W}\sum_{v \in V} \outdegree{v} \weight{v}
\tago{=}
n T - \frac{T}{W} \sum_{v \in V} \sum_{x \in \inneighbors{v}} \weight{x}
\tago{\leq}
n T \parof{1 - \frac{\vc}{W}}.
\end{align*}

Here, in , $\inneighbors{v}$ denotes the in-neighborhood of
$v$. The equality is obtained by implicitly interchanging
sums. is because for each $v$, the sum
$\sum_{x \in \inneighbors{v}} \weight{x}$ is the weighted in-degree
of $v$, and at least $\vc$.  Thus The overall expected running time over
all the sampled roots is

\begin{align*}
\bigO{\prac{W \log{n}}{W - \vc} \evof{\parof{n - \outdegree{\root}}
\bigO{\prac{W \log{n}}{W - \vc} \cdot nT \parof{1 -
\frac{\vc}{W}}}
=                           %
\apxO{n^2 / \eps^2}.
\end{align*}

Meanwhile, when we sample $\bigO{W \log{n} / (W - \vc)}$ vertices in
proportion to their weight, then with high probability, at least one
sampled vertex lies outside the minimum global vertex cut. Such a
vertex then leads to the minimum global vertex cut with high

§.§ Acknowledgement

This project has received funding from the European Research
Council (ERC) under the European Union's Horizon 2020 research
and innovation programme under grant agreement No
715672. Nanongkai was also partially supported by the Swedish
Research Council (Reg. No. 2019-05622). Panigrahi was supported in part
by NSF Awards CCF 1750140 and CCF 1955703.  Quanrud was supported in part by NSF grant CCF-2129816. Cen and Panigrahi  would like to thank Yu Cheng and Kevin Sun for helpful discussions at the initial stages of this project. Quanrud thanks Chandra Chekuri for helpful discussions and feedback.

[1]
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun.
Sparsification of balanced directed graphs.
ICALP, 2021.

[2]
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol
Minimum cuts in directed graphs via \(\surd\)n max-flows.
CoRR, abs/2104.07898, 2021.

[3]
Chandra Chekuri and Kent Quanrud.
Faster algorithms for rooted connectivity in directed graphs.
CoRR, abs/2104.07205, 2021.
To appear in ICALP, 2021.

[4]
Joseph Cheriyan and John H. Reif.
Directed $s$–$t$ numberings, rubber bands, and testing digraph
$k$-vertex connectivity.
Comb., 14(4):435–451, 1994.

[5]
Jack Edmonds.
Edge-disjoint branchings.
Combinatorial algorithms, 1973.

[6]
Shimon Even and Robert Endre Tarjan.
Network flow and testing graph connectivity.
SIAM J. Comput., 4(4):507–518, 1975.

[7]
L. R. Ford and D. R. Fulkerson.
Maximal flow through a network.
Canadian Journal of Mathematics, 8:399–404, 1956.

[8]
Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and
Sorrachai Yingchareonthawornchai.
Computing and testing small connectivity in near-linear time and
queries via fast local cut algorithms.
In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM
Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA,
January 5-8, 2020, pages 2046–2065. SIAM, 2020.

[9]
H.N. Gabow.
A matroid approach to finding edge connectivity and packing
Journal of Computer and System Sciences, 50(2):259–273, 1995.

[10]
Zvi Galil.
Finding the vertex connectivity of graphs.
SIAM J. Comput., 9(1):197–199, 1980.

[11]
Harold Gabow, Zvi Galil, Thomas Spencer, and Robert Tarjan.
Efficient algorithms for finding minimum spanning tree in undirected
and directed graphs.
Combinatorica, 6:109–122, 06 1986.

[12]
Yu Gao, Yang P. Liu, and Richard Peng.
Fully dynamic electrical flows: Sparse maxflow faster than
CoRR, abs/2101.07233, 2021.

[13]
Pawel Gawrychowski, Shay Mozes, and Oren Weimann.
Minimum cut in o(m log\({^2}\) n) time.
In ICALP, volume 168 of LIPIcs, pages 57:1–57:15.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[14]
Pawel Gawrychowski, Shay Mozes, and Oren Weimann.
A note on a recent algorithm for minimum cut.
In SOSA, pages 74–79. SIAM, 2021.

[15]
Andrew V. Goldberg and Robert Endre Tarjan.
A new approach to the maximum-flow problem.
J. ACM, 35(4):921–940, 1988.

[16]
Jianxiu Hao and James B. Orlin.
A faster algorithm for finding the minimum cut in a directed graph.
J. Algorithms, 17(3):424–446, 1994.

[17]
Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow.
Computing vertex connectivity: New bounds from old techniques.
J. Algorithms, 34(2):222–250, 2000.

[18]
David R Karger.
Minimum cuts in near-linear time.
Journal of the ACM (JACM), 47(1):46–76, 2000.

[19]
Andrés López-Martínez, Sagnik Mukhopadhyay, and Danupon
Work-optimal parallel minimum cuts for non-sparse graphs.
SPAA, 2021.

[20]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and
Sorrachai Yingchareonthawornchai.
Vertex connectivity in poly-logarithmic max-flows, 2021.

[21]
Sagnik Mukhopadhyay and Danupon Nanongkai.
Weighted min-cut: sequential, cut-query, and streaming algorithms.
In STOC, pages 496–509. ACM, 2020.

[22]
Yishay Mansour and Baruch Schieber.
Finding the edge connectivity of directed graphs.
Journal of Algorithms, 10(1):76–85, 1989.

[23]
N. Megiddo, Arie Tamir, Eitan Zemel, and Ramaswamy Chandrasekaran.
An $o(n\log^2 n)$ algorithm for the k th longest path in a tree with
applications to location problems.
SIAM Journal on Computing, 10, 05 1981.

[24]
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.
Breaking quadratic time for small vertex connectivity and an
approximation scheme.
In Proceedings of the 51st Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages
241–252, 2019.

[25]
V. D. Podderyugin.
An algorithm for finding the edge connectivity of graphs.
Vopr. Kibern., 2:136, 1973.

[26]
Kent Quanrud.
Fast approximations for rooted connectivity in weighted directed
CoRR, abs/2104.06933, 2021.

[27]
Claus-Peter Schnorr.
Bottlenecks and edge connectivity in unsymmetrical networks.
SIAM Journal on Computing, 8(2):265–274, 1979.

[28]
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron
Sidford, Zhao Song, and Di Wang.
Minimum cost flows, mdps, and $\ell_1$-regression in nearly linear
time for dense instances.
CoRR, abs/2101.05719, 2021.

[29]
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol
Saranurak, Aaron Sidford, Zhao Song, and Di Wang.
Bipartite matching in nearly-linear time on moderately dense graphs.
In 61st IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 919–930.
IEEE, 2020.

[30]
Neal E. Young.
Randomized rounding without solving the linear program.
In Proceedings of the Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA '95, page 170–178, USA, 1995.

§ PROOF OF  APX-REC-SKELETON

For ease of notation, we prove apx-rec-skeleton except
with $\epsmore$ replaced by $(1 + c \eps)$, for a fixed constant
$c > 1$, in properties <ref> and
<ref>. The constant factor can then be removed
by decreased $\eps$ by a constant factor in the construction.

Let $\tau = c_{\tau} \eps^2 \ec / (k \log n)$ for a sufficiently
small constant $c_{\tau} > 0$. Decreasing $c_{\tau}$ by at most a constant factor, we can assume that $\lambda$ and $\eps \lambda / 2k$ are integer multiples of $\tau$. Let $G_0 = (V,E_0)$ be the reweighted subgraph obtained as follows.

* rec-importance-sample Randomly round the weight of
each edge independently up or down to the nearest multiple $\tau$,
preserving the weight of each edge in expectation.[That is, if the weight of an edge $e$ in $G$ is $x\cdot \tau+y$ for an integer $x\geq 0$ and any $0\leq y<\tau$, then the weight of $e$ is  $(x+1)\cdot \tau$ with probability $y/\tau$ and $x\cdot \tau$ otherwise.] Drop any edges with weight rounded down to $0$.

* rec-extra-edges Add an edge of weight
$\eps \lambda / 2k$ from the root $\root$ to every vertex
$v \in V - \root$.

* rec-scale-down Scale down all the edge weights by $\tau$.

For each set $\Sink\subseteq V$, let $w_1(\Sink) = \incutsize{\Sink}{G}$ denote
the weight of the in-cut at $\Sink$ in $G$. Let $w_2(\Sink)$ denote
the randomized weight of the in-cut after randomly rounding in step
rec-importance-sample.  Let $w_3(\Sink)$ denote the
randomized weight of the in-cut of $\Sink$ after adding the
auxiliary edges in rec-extra-edges.  The first claim
analyzes the concentration of $w_2(\Sink)$ for all sets
$\Sink \subseteq V$.

* rec-concentration With high probability, for all
$\Sink \subseteq V$,

\begin{align*}
\absvof{w_2(\Sink) - w_1(\Sink)} \leq \eps w_1(\Sink) + \frac{\eps \lambda
\sizeof{\Sink}}{2 k}.
\end{align*}

The above claim consists of an upper and lower bound on $w_2(\Sink)$ for
all $\Sink$.  We first show the lower bound on $w_2(\Sink)$ holds for all $\Sink$
with high probability.  Fix $\Sink \subseteq V$.  $w_2(\Sink)$ is an
independent sum with expected value $w_1(\Sink)$ and where each term in
the sum is nonnegative and varies by at most $\tau$. By a variation
of standard Chernoff
inequalities[ Here we
apply the following bounds (appropriately rescaled) which follow
from the same proof as the standard multiplicative Chernoff bound.

Let $X_1,\dots,X_n \in [0,1]$ independent random
variables. Then for all $\eps > 0$ sufficiently small and all
$\gamma > 0$,

\begin{align*}
\probof{X_1 + \cdots + X_n \leq \epsless \evof{X_1 + \cdots + X_n} -
\gamma} \leq e^{-\eps \gamma},
\end{align*}

\begin{align*}
\probof{X_1 + \cdots + X_n \geq \epsmore \evof{X_1 + \cdots + X_n} +
\gamma} \leq e^{-\eps \gamma}.
\end{align*}

], for any $\gamma \geq 0$, we have

\begin{align*}
\probof{w_2(\Sink) \leq \epsless  w_1(\Sink) - \gamma} \leq e^{- \eps \gamma /
\tau}
=                           %
n^{- \gamma k \log{n} / c_{\tau} \eps \lambda},
\end{align*}

In particular, for $\gamma = \eps \lambda \sizeof{\Sink} / 2 k$, the RHS is at most

n^- c_0

where $c_0$ is a constant under our control (via $c_{\tau}$). For
large enough $c_0$, we can take the union bound over all sets of
vertices.  This establishes that the lower bounds for $w_2(\Sink)$
hold for all $\Sink$ with high probability. The upper bounds also
hold with high probability by a symmetric argument.

Now we analyze the in-cuts after step
Recall that for $\Sink \subseteq V$, $w_3(\Sink)$ denotes the weight of
the in-cut of $\Sink$ after adding the auxiliary edges in

* rec-padded-concentration With high
probability, for all $\Sink \subseteq V - \root$, we have

\begin{align*}
\epsless w_1(\Sink) \leq w_3(\Sink) \leq \epsmore w_1(\Sink) + \eps \lambda
\sizeof{\Sink} / k.
\end{align*}

Indeed, we have
$w_3(\Sink) = w_2(\Sink) + \eps \lambda \sizeof{\Sink} / 2k$ for all
$\Sink \subseteq V - \root$. The additive term introduced by $h$ offsets
the additive error in the lower bound on $w_2(\Sink)$ in
rec-concentration. This term also adds on to the additive
error in the upper bound of rec-concentration for a total
of $\eps \lambda \sizeof{\Sink} / k$. Thus in the high probability
event of rec-concentration, we have the bounds described
by rec-padded-concentration for all $\Sink$.

Henceforth, let us assume that the high probability event in
rec-padded-concentration holds. (Otherwise the algorithm
fails.) We now argue that rec-padded-concentration implies that properties <ref>, <ref> and <ref> hold whp.

the weight of each $\root$-cut decreases by at most an
$\epsless$-multiplicative factor, the minimum $\root$-cut $\optSink$ has weight at
least $\epsless \incutsize{\optSink}{G}$. Meanwhile $\incutsize{\optSink}$
increases by at most a $\parof{1 + 2 \eps}$-multiplicative
factor. Thus $\incutsize{\optSink}$ remains a $\apxmore$-approximate
minimum $r$-cut.  This establishes property

Since again the weight
of any $\root$-cut decreases by at most an $\epsless$-multiplicative
factor, any $\alpha$-approximate minimum cut in the randomly
reweighed graph $G_0$ is an $\apxmore \alpha$-approximate min $\root$-cut in $G$. This establishes property

Finally, we observe that before
scaling in step rec-scale-down, all edge weights are at least $\tau$, so after scaling, all
edge weights are at least 1. Meanwhile, after scaling, the minimum
$r$-cut has weight at most
$\bigO{\incutsize{T} / \tau} = \bigO{k \log{n} / \eps^2}$. This
establishes property <ref> and completes the

§ PROOF OF <REF>

We start by defining the fractional arborescence packing problem.
Let $A_1,A_2,\ldots, A_N$ be the set of all $s$-arborescences. We represent a fractional packing of arborescences as a vector $x\in \mathds{R}^N$, where $x_i$ represents the fractional contribution of arborescence $A_i$ in the packing.
Define the value of the arborescence packing as the sum of the coordinates of $x$, i.e., $\val(x) := \sum_{i=1}^N x_i$.
The goal is to maximize $\val(x)$, under the constraint that each edge $j$ can be fractionally used only up to its weight $w(j)$.
This definition generalizes integral arborescence packing, where we pack a multiset of arborescences, under the constraint that each edge $j$ is used at most $w(j)$ times, and the value is the cardinality of the multiset.

It will be convenient to state the fractional arborescence packing problem in the framework of a standard packing problem, defined below:

For convex set $P\subseteq \mathds{R}^n$ and nonnegative linear function $f:P\to \mathds{R}^m$, the packing problem aims to find $\gamma^*=\min_{x\in P}\max_{j\in[m]} f_j(x)$, i.e., the solution in $P$ that minimizes the maximum value of $f_j(x)$ over all $j$.  The width of the packing problem $(P, f)$ is defined as $\omega=\max_{j\in[m],x\in P}f_j(x)-\min_{j\in[m],x\in P}f_j(x)$.

For the fractional arborescence packing problem, we have the following: $P=\{x\in \mathds{R}^N : \val(x)=1,x\ge0\}$ is the convex hull of all arborescences. The function $f:P\to \mathds{R}^m$ defines the total usage of each edge $j$ in the arboresence packing normalized by the edge weight, i.e.,  $f_j(x)= \frac{\sum_{i\in[N]: j\in A_i} x_i}{w(j)}$ for $x\in P$ and any edge $j\in [m]$; we call this the load of arborescence packing $x$ on edge $j$.
The packing problem has width

\begin{align}
\omega = \max_{j\in[m],x\in P}f_j(x)-\min_{j\in[m],x\in P}f_j(x) \le \max_{j\in[m]}\frac{1}{w_j}-0 = \frac{1}{w_{\min}}, \label{eq:width bound}
\end{align}

where $w_{\min}$ is the minimum edge weight.
The objective function is to minimize the maximum load: $\gamma^*=\min_{x\in P}\max_{j\in[m]}f_j(x)$.

For any $x\in P$ with maximum load $\gamma=\max_{j\in[m]} f_j(x)$, we can multiply it by $1/\gamma$ to get an arborescence packing with value $1/\gamma$ and maximum load 1.
Conversely, for any fractional arborescence packing $x\in\mathds{R}^N$ with $\val(x)=v$ where $f_j(x)\le1$ for all edges $j$, we have $x/v\in P$.

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.
If the value of maximum $\root$-arborescence packing is $\lambda^*$, then

the optimal value of the packing problem is:

\begin{align}
\gamma^*=\frac{1}{\lambda^*}. \label{eq:gamma star}
\end{align}

Next we describe the packing algorithm (Figure 2 of [30]).  Maintain a vector $y\in \mathds{R}^m$, initially set to $y=\bf{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'$ defined by $y'_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:

After $\lceil\frac{(1+\epsilon)\omega\ln m}{\gamma^*((1+\epsilon)\ln(1+\epsilon)-\epsilon)}\rceil$ iterations of the packing algorithm, $\bar{\gamma}:=\max_j f_j(\bar{x})\le (1+\epsilon)\gamma^*$.

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

The value of maximum $\root$-arborescence packing is equal to the value of $\root$-mincut.

We now prove <Ref>.

First, construct $G_0$ according to <Ref>, with edge size $m_0=\min\{m,O(nk\log n/\epsilon^2)\}$. Let $\lambda_0$ denote the minimum $s$-cut value on $G_0$. <Ref> guarantees

\begin{align}
w_{\min}\ge 1 \mbox{ and } \lambda_0 = O(k\log n/\epsilon^2). \label{eq:lambda 0 upper bound}
\end{align}

By the duality (<Ref> and (<ref>)),

the optimal value of the packing problem formulated above is  $\gamma^*=\frac{1}{\lambda_0}$.

Run the aforementioned arborescence packing algorithm. <Ref>, (<ref>),(<ref>) and (<ref>) guarantee that after

$$O\left(\frac{\omega \ln m}{\gamma^*}\right)=O\left(\frac{\lambda_0\ln m}{w_{\min}}\right)= O(\lambda_0\ln m)= O(k \log^2 m)$$

iterations (with constant $\epsilon$) we have

\begin{align}
\bar{\gamma}&\le(1+\epsilon)\gamma^*.
\end{align}

Then $\bar{x}/\bar{\gamma}$ is an arborescence packing with value $1/\bar{\gamma}\ge \frac1{1+\epsilon}\lambda_0$.

Consider sampling a random $s$-arborescence $A$ from distribution $\bar x$, so we choose arborescence $A_i$ with probability $\bar x_i$. Since $\delta_{G_0}^-(\optSink) \le (1+\epsilon)\lambda_0$ by <Ref>,  the expected number of edges in $A\cap\partial_{G_0}^-(\optSink)$ is at most $(1+\epsilon)\lambda_0 / (\frac{1}{1+\epsilon}\lambda_0) = (1+\epsilon)^2\le 1+3\epsilon$ for small enough constant $\epsilon$.  Since we always have $|A\cap\partial_{G_0}^-(\optSink)|\ge1$, by Markov's inequality $\Pr[|A\cap\partial_{G_0}^-(\optSink)|-1\ge 1]\le 3\epsilon \le 1/2$ for small enough constant $\epsilon$.  Therefore, if we uniformly sample $\Theta(\log n)$ arborescences from the distribution $\bar x$, at least one of the arborescences is 1-respecting whp.

It remains to compute $x=\arg\min_{x\in P}\sum_j y_j f_j(x)$ on each iteration. Since $\sum_jy_jf_j(x)$ is linear in $x$, the minimum must be achieved by a single arborescence.  So the task reduces to computing the minimum cost spanning $s$-arborescence, which can be done in $O(m_0+n\log n)$ [11]. The total time complexity, over all iterations, becomes $O((m_0+n\log n)\lambda_0\log n) = O(\min\{mk\log^2 n,nk^2\log^3 n\})$.  The construction of <Ref> costs another $O(m\log n)$ time.

§ PROOF OF APX-RVC-SPARSIFICATION

Sparsifying a graph to preserve the rooted vertex

$\tau = c_{\tau} \eps^2 \vc / k \log{n}$ and let
$\Delta = c_{\Delta} k \log{n} / \eps^2$, where $c_{\tau} > 0$
is a sufficiently small constant and $c_{\Delta} > 0$ is a
sufficiently large constant.    rvc-first-step

Randomly round each vertex
weight to (nearest) multiples of $\tau$. rvc-importance-sample

For each vertex $v$,
introduce an auxiliary vertex $a_v$ with weight
$\eps \vc / 2 k$. Add edges from the $\root$ to $a_v$, and from
$a_v$ to $v$.    rvc-extra-vertices

Decreasing $c_{\tau}$ and $\eps$ as needed, we
assume that $\vc$ and $\eps \vc / 2k$ are multiples of

Remove all outgoing edges from any vertex with weight $0$.

Scale down all vertex weights by $\tau$ (which makes them integers).  rvc-rescale

Truncate all vertex weights to be
at most $c_{w} k \log{n} / \eps^2$ for a sufficiently large
constant $c_w > 0$.   rvc-truncate

For all $v$ with unweighted in-degree at
least $\Delta$, replace all incoming edges to $v$ with a single
edge from $\root$.   rvc-contract

Consider the Algorithm <ref> applied
to the input graph $G$.  Let $\sparseG$ be the graph obtained at the
end of the algorithm. Properties <ref> through
<ref> follow directly from the construction. The remaining
proof is dedicated to proving the high probability bounds of
<ref> and <ref>. We first show
that the initial steps <Ref> to rvc-extra-vertices

– before rescaling – preserves the
minimum weight rooted vertex-cut approximately in the sense of
<ref> (sans scaling). We then analyze the remaining
steps.  For each set $S$, let $w_1(S)$ denote the weight of the vertex
in-cut of $S$. Let $w_2(S)$ denote the randomized weight of the vertex
in-cut after step rvc-importance-sample. Let $w_3(S)$ denote
the randomized weight of the vertex in-cut after step

* rvc-concentration
With high probability, for all $S \subseteq V$, we have

\begin{align*}
\absvof{w_2(S) - w_1(S)} \leq \eps w_1(S) + \frac{\eps \vc \sizeof{S}}{2k}.
\end{align*}

The claim and proof are similar to rec-concentration in
the proof of apx-rec-sparsification. The claim consists
of an upper bound and a lower bound on $w_2(S)$ for all $S$ and we
first show the lower bound holds with high probability.  Fix any set
$S$.  $w_2(S)$ is an independent sum with expected value $w_1(S)$ and
where each term in the sum is nonnegative and varies by at most
$\tau$. Concentration bounds (see footnote
<ref> on page
footnote:additive-chernoff) imply that for any
$\gamma \geq 0$, we have

\begin{align*}
\probof{w_2(S) \leq \epsless  w_1(S) - \gamma} \leq e^{- \eps \gamma /
\tau}
=                           %
n^{- \gamma k \log{n} / c_{\tau} \eps \vc},
\end{align*}

In particular, for
$\gamma = \eps \vc \sizeof{S} / 2 k$, the RHS is at most

n^- c_0 S

where $c_0 > 0$ is again a constant under our control (via
$c_{\tau}$). For sufficiently large $c_0$, we can take the union
bound over all sets $S$, establishing the high probability lower
bound. The high probability upper bound follows by a symmetric

Now we analyze the vertex $\root$-cuts after step
Recall that for $S \subseteq V$, $w_3(S)$ denotes the weight
of the in-cut of $S$ after adding auxiliary vertices in step

* rvc-padded-concentration For all
$S \subseteq V'$, we have

\begin{align*}
\epsless w_1(S) \leq w_3(S) \leq \epsmore w_1(S) + \frac{\eps \vc\sizeof{S}}{k}.
\end{align*}

This claim and its proof is similar to
rec-padded-concentration in
apx-rec-sparsification.  We have
$w_3(S) = w_2(S) + \eps \vc \sizeof{S} / 2 k$ for all
$S \subseteq V'$.  The additive factor of
$\eps \vc \sizeof{S} / 2 k$ combine with the high-probability
additive error in rec-concentration to establish the

We point out that rvc-padded-concentration implies that,
with high probability after step rvc-extra-vertices, the
weights of all the vertex $\root$-cuts are preserved in the approximate
sense described by <ref> (without the scaling).
Henceforth we assume that the high probability event of
rvc-padded-concentration holds.  Now, after step
rvc-extra-vertices, all the weights are integer multiples
of $\tau$. We have $\vc / \tau = \bigO{k \log{n} / \eps^2}$.  After
scaling down by $\tau$ in step rvc-rescale, we still
preserve the $\root$-cuts per property
<ref>. Truncating weights in $\sparseG$ to
$\bigO{\vc / \tau}$ decreases the weight of some cuts, but to no
less than $\bigO{\vc / \tau}$ (which maps to $\bigO{\vc}$ when
rescaled back to the scale of $G$). Removing the outgoing edges of
vertices with weight $0$ also has no impact on the weight of any
vertex $\root$-cut. The final step adding edges from $\root$ only eliminates
some of the vertex $\root$-cuts from consideration and does not impact
the weight of the remaining vertex $\root$-cuts. This establishes

It remains to prove <ref> and in particular we
must show that it is not impacted by the last step,
rvc-contract.  Recall that step rvc-contract
replaces the incoming edges to any vertex $v$ with unweighted
in-degree greater than $\Delta = \bigO{k \log{n} / \eps^2}$ with a
single edge in $\root$.  In particular, this edge places $v$ in
$\outneighbors{\root}$ and destroys all $\root$-cuts where the sink
component contains $v$.  Let $\Sink \subset V'$ be the sink
component of a vertex $\root$-cut in $G$ where the capacity of the cut
is at most $\vc$, and $\sizeof{\Sink} \leq k$.  We want to show that
all vertices in $\Sink$ have in-degree less than $\Delta$, in which
case the extra edges in rvc-contract have no impact on
$\Sink$.  The vertex in-cut induced by $\Sink$ has weight at most
$(1 + 2 \eps) \vc / \tau$ in the randomized graph before
rvc-contract (per <ref>).  Fix any
$v \in \Sink$ and consider the edges going into $v$. At most $k - 1$
of those edges can come from another vertex in $\Sink$, since
$\Sink$ has at most $k$ vertices. The remaining edges must be from
vertices in the vertex in-cut of $\Sink$.  Each of these vertices
have weight at least $1$, and by <ref> the in-cut
has weight at most $(1 + 2 \eps) \vc / \tau$, so there are at most
$\bigO{\vc / \tau}$ of these vertices.  This gives a maximum total
of less than $\Delta$ edges incident to $v$, as desired.  In
conclusion, for any vertex $v$ that is the endpoint to at least
$\Delta$ edges, it is safe to replace all of $v$'s incoming edges
with a single edge from the root, without violating
<ref>. This establishes
<ref> and completes the proof.

This section has some notes by Kent made while making the initial

* There is an environment  which defines a bunch of
macros that Kent's writing depends on. (The environment ensures
these commands do not effect the rest of the document.)

* I (Kent) dumped the old sections on edge connectivity and intro in the
appendix in case we wanted to use any part of it.

* I put in the references from my manuscript only for the time
being while we edit and integrate things, and plan to clean it up or remove it later.

* I placed my  and  source files in the
subfolder krq.

* The edge sparsification lemma was pulled out and put in its own

* I haven't done too much rewriting / glue work yet - my first goal
was just to get it in there and compiling.

§.§ Updated May 26

Kent's todo

* (First pass done) Smoothen over vertex connectivity.

* (Done) Refine edge sparsification ($\eps$'s, etc).

* (Still checking) Don't forget to double check references throughout paper if I change anything.

* (Done) Paragraph (or so) for approximate edge connectivity.

* (To do) Pass over intro, extend with approximation ideas

* (Did some in related work) Bring in references for vertex connectivity

* A little less on max flow, a little more on ideas for vertex connectivity.

Other notes:

* $o(mn)$?

* "rooted Steiner trees" in input graph, or arboresences in contracted graph.

§.§ Notation

All in all, I (Kent) did not spot many differences in notation. Here
are some notes (that I have not acted upon.)

* You guys use $\partial{S}$ for the out-cut of $S$ while I used

* I frequently used $k$ as a parameter represented the number of
vertices in the sink component whereas you guys used
$\theta \sqrt{n}...$ for a parameter $\theta$. As I understand the
right choice of $k$ will vary for different settings (and no longer
coincides with $\sqrt{n}$, for the exact setting).

I wasn't sure whether or how to integrate this - in any case, I
kept this in the appendix in case we wanted to use some parts of
it.Let $G = (V,E)$ be a directed graph with $m$ edges and $n$
vertices.  Let $G$ have positive edge weights $w: E \to \preals$.
Recall that $G$ is strongly connected if any vertex can reach
any other in the graph.  The (global, weighted) edge connectivity is
the minimum weight of edges that needs to be removed so that $G$ is no
longer strongly connected.  The minimum (weight) cut is the
corresponding set of edges.  Determining the edge connectivity and
computing the minimum cut are basic problems in graph algorithms.
This work develops a faster randomized algorithm for approximating the
minimum weight cut.

The algorithm for edge connectivity is developed alongside for the
following related connectivity problems also of basic interest.  Let
$r \in V$ be a fixed vertex, called the root.  The
minimum rooted cut (from $r$), also called the minimum
$r$-cut, is the minimum weight set of edges whose removal
disconnects $r$ from at least one vertex.  Global connectivity follows
from rooted connectivity by choosing any root arbitrarily, and
computing the rooted connectivity in both $G$ and the reversed graph.
Most of the algorithmic discussion in this work is focused on rooted
connectivity and global connectivity is obtained as a by-product.
Rooted connectivity has other connections in combinatorial
optimization <cit.>; for example,
<cit.> showed that the $r$-rooted edge connectivity equals
the maximum number of arboresences rooted at $r$ that can be packed
into the graph.  Now suppose instead that the graph has vertex weights
$w: V \to \preals$. The (global) vertex connectivity is the
minimum weight of vertices that needs to be removed so that $G$ either
is no longer strongly connected or consists of only a single vertex;
the minimum vertex cut is the corresponding set of vertices.  One can
also define rooted vertex connectivity analogously to rooted edge
connectivity.  This work also develops fast approximation algorithms
for rooted and global vertex connectivity.

These connectivity problems are well-studied and we first give an
overview of classical results, with particular focus on algorithms for
directed graphs, before discussing more recent developments.  There is
a long line of algorithms for directed edge connectivity
(see also <cit.>), of which we highlight the most
pertinent.  For general weights, an algorithm by <cit.>
finds the minimum rooted cut in $\bigO{m n \log{n^2 / m}}$ time.  For
multigraphs, <cit.> gives an
$\bigO{m \lambda \log{n^2 / m}}$ time algorithm for the minimum
$r$-cut, where $\lambda$ is the weight of the minimum rooted cut.
Directed vertex connectivity likewise has had many algorithms, and
many of these running times are parametrized by the weight of the
vertex cut
Of those that are not, we highlight the randomized
$\bigO{m n \log{n}}$ time algorithm of 17 that remains the
fastest algorithm in weighted and directed graphs.

Recently there has been a flurry of results for graph algorithms
several of which impact directed connectivity.  There have been many
significant developments for $(s,t)$-flow for both edge- and
vertex-capacitated directed graphs.
<cit.>.  Very recently
<cit.> obtained an $\apxO{m + n^{1.5}}$ running time for
edge-capacitated $(s,t)$-max flow, generalizing a preceding
$\apxO{m + n^{1.5}}$ algorithm for vertex capacitated $(s,t)$-max flow
[29].[Here and throughout $\apxO{\cdots}$ hides
polylogarithmic factors. The algorithms in this work use the
$\apxO{m + n^{1.5}}$ time algorithms <cit.> as a
subroutine which incur large polylogarithmic factors hidden in the
$\apxO{\cdots}$ notation. Consequently we generally do not try to
optimize polylogarithmic factors in this article.]

Another recent development is a randomized $\apxO{m \vc^2}$ time exact
algorithm and a randomized $\apxO{m \vc / \eps}$ time
$\epsmore$-approximation for global vertex connectivity in unweighted
directed graphs [8].  These algorithms are based on
local algorithms for vertex connectivity and influence the local
algorithms that appear in this work.  A very recent and independent
work of [20] has obtained an $\apxO{m n^{1-1/12 + o(1)}}$ time
algorithm for vertex connectivity in directed and unweighted
graphs. (We have not yet had time to digest and make a proper
comparison to [20].)  The last recent work we discuss is a
randomized, $\apxO{n^2 U^2}$ time (exact) algorithm for rooted and
global edge connectivity in directed graphs with small integer
capacities between $1$ and $U$
[3]. [3] also
gives a $\apxO{\vc n W}$-time exact algorithm for rooted and global
vertex capacity with integer weights, where $W$ is the total weight in
the graph, and $\vc$ is the weight of the minimum vertex cut.
[3] introduces elementary ideas to sparsify
rooted connectivity problems but the crux of the argument needs the
capacities to be small.  The driving motivation of this article is to
overcome the limitations of [3] to small
integer capacities and extend the ideas to the weighted setting.

§.§ Results.
The primary results of this work extend the
$\apxO{n^2}$ randomized running times of
[3] to the weighted setting while
allowing for approximation. These algorithms take as input an
additional parameter $\eps > 0$; the goal is to compute a cut
whose weight is at most a $\epsmore$-multiplicative factor
greater than the minimum cut.

Edge connectivity. The first result is for rooted and
global edge connectivity.

Given a directed graph with polynomially
bounded weights, and $\eps \in (0,1)$, a $\epsmore$-approximate
minimum rooted or global edge cut can be computed with high
probability in $\apxO{n^2 / \eps^2}$ randomized time.

It is of theoretical interest to obtain $o(mn)$ running times due to
the longstanding $\bigO{m n \log{n^2 / m}}$ running time of
<cit.> and the connection to flow decompositions.  Observe
that the above running time for edge connectivity is $o(mn)$ except
for the case where $m \leq n^{1+ o(1)}$.  One can modify the algorithm
in apx-ec (leveraging, in particular, the recent
$m^{1.5 - 1/28}$ time algorithm for $(s,t)$-flow [12]) to
establish a $o(mn)$ running time, as follows.

There exists a constant
$c > 0$ such that, for all fixed $\eps > 0$, an
$\epsmore$-approximate minimum weight rooted or global cut in
a directed graph with polynomially bounded edge weights can be
computed with high probability in
$\bigO{(mn)^{1-c} / \eps^{2}}$ randomized time.

Vertex connectivity.
The other main result is for rooted vertex connectivity. Here,
$\outdegree{v}$ denotes the unweighted out-degree of a vertex $v$.

Let $\eps \in (0,1)$, let $G = (V,E)$ be a
directed graph with polynomially bounded vertex weights, and let
$r \in V$ be a fixed root. A $\epsmore$-approximate minimum vertex
$r$-cut can be computed with high probability in
$\apxO{m + n (n - \outdegree{r}) / \eps^2}$ randomized time.

An argument by [17] (with some modifications) implies that
the above running time for rooted vertex connectivity, combined with
randomly sampling roots by weight, leads to the following running time
for global vertex connectivity.

For all $\eps \in (0,1)$, a
$\epsmore$-approximate minimum weight global vertex cut in a
directed graph with polynomially bounded vertex weights can be
computed with high probability in $\apxO{n^2 / \eps^2}$ expected

In the same way as for edge connectivity above, apx-rvc
and apx-vc leads to $o(mn)$ time approximation
algorithms for rooted and global vertex connectivity, as follows.

There exists a constant
$c > 0$ such that, for all fixed $\eps > 0$, an
$\epsmore$-approximate minimum weight rooted or global cut in
a directed graph with polynomially bounded edge weights can be
computed with high probability in
$\bigO{(mn)^{1-c} / \eps^{2}}$ randomized time.

§.§ Key ideas.

We can readjust this to give an overview to the vertex
connectivity algorithms instead.The high level approach is inspired
by previous work in [3], which was limited
to small integer capacities.  Let us focus on edge connectivity as the
ideas for vertex connectivity are similar.  An important idea that
emerges from [3] is that there are useful
tradeoffs based on the number of vertices in the sink component.  Let
$k$ denote the number of vertices in the sink component of the minimum
$r$-cut, and for simplicity, suppose $k$ is known.
[3] observed that if $k$ is small, and the
graph has small capacities, then the graph can be sparsified by
contracting vertices with in-degree greater than $\bigO{k}$ into the
root.  Meanwhile, if $k$ is large, then it is easier to sample a
vertex from the sink component and then apply $(s,t)$-flow.  Balancing
these tradeoffs leads to an $\apxO{n^2}$ time exact algorithm for
rooted edge connectivity (for small integer capacities).  Note that
the sampling approach for large $k$ extends to the weighted
setting. However the sparsification argument requires the assumption
of small capacities.  The high-level goal of this work is to extend
the ideas from [3] to the weighted setting.

The first step is to take advantage of the approximation error and
discretize the edge weights (and also reduce the number of edges) by
random sampling.  While random sampling is known to preserve cuts in
undirected graphs <cit.>,
there are no such guarantees in directed graphs.  Here we continue the
theme of balancing tradeoffs in the size of the sink component, $k$.
Rather than sampling as to preserve all cuts, we only sample to
preserve the in-cuts of vertex sets of size less than or equal to $k$
of the minimum rooted cut (which can be guessed).  This requires
paying some overhead in proportion to the target component size.  To
address large vertex sets for which the random sampling might
drastically understimate the in-cut, we add appropriately weighted
auxiliary edges from the root to every vertex. The auxiliary edges
make it impossible for large vertex sets to induce the minimum weight
rooted cuts, but also have limited impact on small vertex sets. (This
approach is inspired in part by the sparsification ideas in
[3] and in another part by the pessimistic
estimator in <cit.>.)  Thereafter one can contract high-degree
nodes in the root similar to [3].  The end
result is a sparser graph where the sparsity depends on $k$.
Moreover, up to scaling, the sparsified graph has integer capacities,
and the weight of the minimum $r$-cut becomes proportional to $k$.

In this sparsified graph, depending on the (guessed) size of the sink
component, the algorithm pursues one of two options.  If $k$ is
smaller than (roughly) $\sqrt{n}$, the graph is very sparse and the
size of the cut is small, and we run an algorithm based on a new
deterministic local cut algorithm that takes advantage of the small
value $k$. If $k$ is larger, then we try to sample a vertex from the
sink component and run $(s,t)$-flow.  In both cases we work in the
sparsified graph.  Balancing terms between the running times of these
two approaches leads to the claimed $\apxO{n^2 / \eps^2}$ running

We highlight that in previous work for small capacities, in the regime
where $k$ is small, [3] was able to use
Gabow's algorithm (on a sparsified graph) to find the minimum rooted
cut. Here, in the presence of capacities (even after sparsification),
Gabow's algorithm has a larger polynomial dependency on $k$ than
desired and one needs new ideas.  The local cut approach developed
here is inspired by the recent randomized algorithms of
[8, 3]. Compared to these previous
works, the new local cut algorithm has a better dependency on $k$ and
$\eps$ and is also deterministic.  The local cut algorithm routes flow
in the reversed graph from a fixed vertex $t$ to the root, with
localized running times depending only on $k$.  It takes advantage of
auxiliary edges from the root added in the sparsification step to find
short augmenting paths.  The improved running time comes from a
refined analysis based on how many of these auxiliary edges have been
saturated.  The fact that we are always routing flow to the root also
removes the guess work from [8, 3]
and makes the algorithm deterministic.[That said, the overall
algorithm for rooted edge connectivity is still randomized.]

The remainder of this article is divided into two
sections. apx-ec considers edge connectivity, and proves
apx-ec and
flow-barrier-apx-ec. apx-vc considers
vertex connectivity, and proves apx-rvc,
apx-vc, and flow-barrier-apx-vc.

I'm pretty sure that $\eps^2$-dependency can also be obtained
via arboresences, but I am leaving this here for the time being in
case any parts of the writing might be helpful. In this section, we
design and analyze an $\apxO{n^2 / \eps^2}$-time approximation
algorithm for the minimum weight rooted edge cut.  Here the point of
emphasis is the improved dependency on $\eps$.  We present the
algorithm as three main steps. Each of the steps are parameterized by
values $\lambda > 0$ and $k \in \naturalnumbers$ that, in principle,
are meant to be constant factor estimates for the weight of the
minimum rooted cut and the number of vertices in the sink component of
the minimum rooted cut, respectively. The first step is the
sparsification result (apx-rec-sparsification) that
(assuming $\lambda$ and $k$ are accurate) reduces the problem to a
rooted graph with roughly $nk$ edges and rooted connectivity roughly
$k$ in addition to a few other helpful properties. This sparsification
procedure is used by both of the remaining two steps.  The second
step, preferable for small $k$, approximates the minimum rooted cut in
roughly $nk^2$ time, and is based on a new deterministic local cut
algorithm that makes essential use of some of the specific properties
of the sparsification lemma. The third step, preferable for large $k$,
approximates the minimum rooted cut in roughly $n^2 + n^{2.5}/k$ time,
via random sampling and $(s,t)$-flow in the sparsified
graph. Balancing terms leads to the claimed running time.

Rooted connectivity for large sink components.
The second subroutine we present is better suited for cases where the
sink component is very large.

apx-rec-big-sink Let $G = (V,E)$ be a directed graph
with positive edge weights.  Let $r \in V$ be a fixed root.  Let
$\eps, k, \ec > 0$ be given parameters with $\eps$ sufficiently
small.  Let $\optec$ be the minimum weight of all $r$-cuts where the
sink component has between $k/2$ and $k$ vertices.  Then there is a
randomized $\apxO{n^2 / \eps^2 + n^{2.5} / k}$ time algorithm that
has the following guarantee. If $\optec \leq \ec$, then with
probability, the algorithm returns an $r$-cut of capacity at most
$\optec + \eps \ec$.

We assume the graph $\sparseG = (\sparseV, \sparseE)$ produced by
apx-rec-sparsification with parameters $k$, $\ec$, and
$c \eps$ for a sufficiently small constant $c > 0$.  Let
$\optSink \subseteq V - r$ be the sink component of the minimum
$r$-cut subject to $k/2 \leq \sizeof{\optSink} \leq k$, and suppose
the capacity of $\optSink$ is at most $\ec$.  We randomly sample
$\bigO{n \log{n} / k}$ sinks $t \in \sparseV$, and for each compute
the minimum $(r,t)$ cut. We output the minimum of these cuts.

If $\optec \leq \ec$, then apx-rec-sparsification asserts
that with high probability we have $\optSink \subseteq \sparseV$.
With high probability, some $t$ will be drawn from $\optSink$ and
the corresponding $(r,t)$-cut has capacity at most
$\epsmore \optec + \eps \lambda$.  We use
$\ectime{m}{n} = \apxO{m+n^{1.5}}$ <cit.>.  By
apx-rec-sparsification, we have
$m = \bigO{n k \log{n} / \eps^2}$.

Rooted and global edge connectivity.
Finally we combine the two approaches above for rooted connectivity –
apx-rec-small-sink for small components, and
apx-rec-big-sink for large components – in an overall
algorithm for rooted edge connectivity and establish
apx-ec. We restate apx-ec for the sake of
convenience.In the original manuscript, this was restated from
the introduction.

apx-ec Given a directed graph with polynomially
bounded weights, and $\eps \in (0,1)$, a $\epsmore$-approximate
minimum rooted or global edge cut can be computed with high
probability in $\apxO{n^2 / \eps^2}$ randomized time.

We focus on rooted connectivity from which global connectivity
follows immediately.  As the weights are polynomially bounded, we
can guess the rooted connectivity $\lambda$ and the number of
vertices $k$ in the sink component of the minimum rooted cut up to a
multiplicative factor of 2 with polylogarithmic overhead. For each
choice of $k$, we apply the faster of apx-rec-small-sink
and apx-rec-big-sink.  We balance the

n k^2 / ^4

running time of apx-rec-small-sink with the

n^2 / ^2 + n^2.5 / k

running time of apx-rec-big-sink.  For
$k = \sqrt{n} \eps^{4/3}$, we obtain the claimed running time.

We now show how to approximate rooted and global vertex connectivity
in $o(mn)$ time, just as we did previously for edge connectivity. We
point out that the minimum $(s,t)$-edge cut algorithm of [12]
that runs in $\apxO{m^{1.5 - \delta}}$ time for $\delta = 1/128$ is
also an $\apxO{m^{1.5 - \delta}}$ time algorithm for $(s,t)$-vertex
cut by standard reductions. As the ideas here to develop an $o(mn)$
time approximation for vertex connectivity are the same as for edge
connectivity, we restrict ourselves to a sketch.

sparse-apx-vc Let $\eps \in (0,1)$, and let $G = (V,E)$
be a directed graph with polynomially bounded vertex weights.
Suppose that the minimum $(s,t)$-vertex cut can be computed in
$\apxO{m^{3/2-\delta}}$ time for a constant $\delta > 0$. For a
fixed root $r \in V$, a $\epsmore$-approximate minimum vertex
$r$-cut can be computed with high probability in
$\apxO{m + (n - \outdegree{r}) m^{1 - 2\delta/3} / \eps^{4/3}}$
randomized time. A $\epsmore$-approximate minimum global vertex cut
can be computed with high probability in
$\apxO{m + n m^{1 - 2 \delta/3} / \eps^{4/3}}$ randomized time.

We first consider rooted vertex cuts. We take the same approach as
apx-rvc except modifying the algorithm
apx-rvc-big-sink as follows. First, we do not sparsify
the graph. Second, we use the $\apxO{m^{3/2 - \delta}}$ time
algorithm for $(s,t)$-vertex cut instead of $\apxO{m +
n^{3/2}}$. The result replaces the running time in
apx-rvc-big-sink with
$\apxO{(n - \outdegree{r}) m^{3/2 - \delta} / k}$. Choosing $k$ to
balance this running time with the
$\apxO{(n - \outdegree{r}) k^2 \log{n} / \eps^4}$ running time of
apx-rvc-small-sink gives the claimed running time.

The running time for global vertex connectivity follows from rooted
connectivity in the same way as apx-vc above.

Balancing sparse-apx-vc with apx-rvc and
apx-vc gives $\apxO{(mn)^{1-c} / \eps^2}$ running times
for approximating rooted and global vertex cuts, where $c> 0$ is a
constant, as claimed in flow-barrier-apx-vc.