References
1 Introduction
intro
Let be a simple directed graph; that is, a directed graph with no parallel edges. Recall that is strongly connected if there is a path from any vertex to any vertex . The edge connectivity is the minimum number of edges that need to be removed so that is not strongly connected. The corresponding set of edges is called the minimum edge cut. The vertex connectivity is the minimum number of vertices that need to be removed so that the remaining graph is not strongly connected or has only one vertex. The corresponding set of vertices is called the minimum vertex cut. These problems generalize to weighted settings where the edges and vertices are assigned positive weights and the goal is to find the minimum weight edge or vertex cut. Determining the edge and vertex connectivities and finding the corresponding minimum cuts are among the basic problems in graph algorithms. This work obtains faster randomized algorithms for finding minimum edge and vertex cuts in directed graphs, especially in the dense setting. The algorithms are based on a simple technique which could be of independent interest.
Our interest is actually in the more general rooted connectivity problems. Let be a fixed vertex, called the root. The rooted edge connectivity is the minimum number of edges that have to be removed so that there is some vertex in that cannot reach. An algorithm for rooted edge connectivity easily implies an algorithm for edge connectivity, by fixing any root and returning the minimum of the rooted connectivity in and the rooted connectivity in the graph obtained by reversing all the edges in . Another important motivation for investigating rooted connectivity is the fundamental result by Edmonds [edmonds70] that the rooted edge connectivity equals the maximum number of edgedisjoint arboresences rooted at . We refer the reader to [schrijver, frank]
for further connections in combinatorial optimization. Similarly, the
rooted vertex connectivity is the minimum number of vertices (excluding ) that have to be removed so that cannot reach some vertex in the residual graph. Algorithms for rooted vertex connectivity also lead to global vertex connectivity by a similar but somewhat more involved reduction. There is a long and rich history of developing algorithms for determining the edge and vertex connectivity. We first note that all of these connectivity and cut problems reduce to a polynomial number of cut and flow problems by standard reductions. Beyond flow, an interesting algorithmic landscape emerges with different running times depending on whether we are interested in edge or vertex cuts, directed or undirected graphs, and weighted or unweighted graphs.Rooted and global edgeconnectivity:
We first discuss edge connectivity in directed graphs. Let denote either the rooted or global edge connectivity of the graph depending on the context. One can compute both via minimum cut computations. For the simple and unweighted directed graph setting, Mansour and Schieber [mansourschieber] improved on this and gave algorithms that run in time or in time for global connectivity. It was also observed by Alon (cf. [mansourschieber]) that this approach can be parameterized by the minimum outdegree to obtain a algorithm, where denotes the running time for edge connectivity^{1}^{1}1Depending on the context, we let denote the running time for cut in either a simple or a weighted directed graph with edges and vertices.. Gabow [gabow] then gave a for rooted connectivity in graphs with integer capacities. Gabow’s algorithm is based on Edmonds’ theorem described above. Gabow’s algorithm is nearly linear time for sparse unweighted graphs, and remains the fastest algorithm for small for both rooted and global edge connectivity. It is interesting that Gabow’s algorithm is not based on flow. For directed graphs with arbitrary edge capacities, Hao and Orlin [haoorlin] gave an algorithm for rooted connectivity by adapting the pushrelabel max flow algorithm; in fact their algorithm computes the connectivity for all . Thereafter there have been no direct running time improvements to rooted or global edge connectivity in directed graphs but we point out that there have been numerous breakthroughs in the running times for flow and connectivity [goldbergrao, orlin13, leesidford, madry13, madry16, liusidford20, kls20, brand++, glp21]. In particular, starting with the work of Goldberg and Rao [goldbergrao], the running time for flow is which breaks the flowdecomposition barrier. Motivated by these developments and several others, there has been a resurgence of interest and literature on faster graph algorithms for several fundamental problems. Despite these developments there has been no algorithm for rooted edgeconnectivity in simple directed graphs that is faster than in the worst case. In this paper we obtain a nearly quadratic time algorithm which also applies to graphs with small integer capacities.^{2}^{2}2Here and throughout hides polylogarithmic factors in and . We note that the ideas introduced in this work are simple and the logarithmic factors they generate are easy to account for. However main also uses the recent flow algorithm of [brand++] with running time , which has large logarithmic factors.
[] main Let be a simple directed graph with edges , vertices, and integer edge weights . Then the minimum rooted
cut can be computed with high probability in
randomized time.Trivial. Also holds for rooted connectivity.  

Matula [matula87]. Also holds for rooted connectivity.  
Mansour and Schieber [mansourschieber]  
*  Alon (cf. Mansour and Schieber [mansourschieber]). is the minimum outdegree in the graph.  
*  Gabow [gabow]. Also holds for rooted connectivity.  
*  main. Randomized. Also holds for rooted connectivity. 
This running time is particularly compelling when the rooted edge connectivity is high.
Rooted and global vertexconnectivity:
We now consider (rooted) vertex connectivity in directed graphs. It is well known that for fast algorithms, global vertex connectivity is more involved than edge connectivity and the running times are more varied. While the rooted vertex connectivity can be reduced to computing cuts, the global version, if done naively, would require calls to the cut problem since it is not obvious how to find a vertex that is not part of the minimum global vertex cut. There is a large body of literature and we highlight the leading (randomized) running times, where we state running times for randomized algorithms with high probability of success. Let denote the weight minimum vertex cut, where we assume the minimum weight of any vertex is 1. For large and general capacities, there is a randomized algorithm by Henzinger [ghr] (extending the directed edge connectivity algorithm of [haoorlin]) that runs in time. For small values of in the unweighted setting, recent randomized algorithms by Forster [fnsyy] based on local connectivity have obtained and running times. For more intermediate values of , there are also randomized and time algorithms [nsy] as well as an time algorithm [cheriyanreif], where is the current exponent for fast matrix multiplication [almanvw]. There is also recent interest in obtaining fast approximation algorithms for minimum vertex cut [nsy, fnsyy]. In particular [fnsyy] obtains a randomized algorithm with running time . Here too we can ask whether one can obtain algorithms that beat in the worstcase for rooted and global vertex connectivity in directed graphs, even when allowing for a constant factor approximation. We obtain the following theorem.
[] simplevcrooted rootedvcreduction Let be the rooted vertex connectivity from . Let be the total weight of the graph. For any a approximate rooted minimum vertex cut can be computed with high probability in randomized time; for unit weights this is . The rooted connectivity can be computed with high probability in time. Note that in the above running times. We point out that the approximation algorithm’s running time is independent of . This large regime has been challenging for previous approaches. The rooted connectivity algorithm, when combined with sampling and other ideas, gives the following theorem for global vertex connectivity. As we remarked, the reduction from global to rooted is not as clean for vertex connectivity as it is for edge connectivity.
[] simplevcglobal Let be the total vertex weight of the graph. Let be the global vertex connectivity of . There is a randomized algorithm that for any outputs a approximate minimum vertex cut with high probability in time . There is a time randomized algorithm that computes the (exact) minimum vertex cut with high probability. In particular, for unit weights, the running time is .
Trivial.  

Trivial. Randomized.  
Podderyugin [podderyugin], Even and Tarjan [eventarjan]  
Cheriyan and Reif [cheriyanreif].  
,  Henzinger [ghr]. 
Henzinger [ghr]. Randomized.  
Gabow [gabow06].  
,  Nanongkai [nsy]. Randomized. 
,  Forster [fnsyy]. Randomized. 
simplevcglobal. Randomized. 
1.1 Key ideas
Our algorithms are based on a simple but key idea that we briefly outline below. We focus on the edgeconnectivity case since the idea for vertex connectivity is essentially the same with some modifications. We would like to take advantage of recent developments on fast algorithms for cut and reduce to solving a small number of such cut problems in a black box fashion (unlike the approach of [haoorlin] based on the properties of a specific flow algorithm). For undirected graph global connectivity there has been very recent exciting progress by Li and Panigrahi [lipanigrahi] reducing to a logarithmic number of cuts. However, the technique makes strong use of the symmetry of the edgecut function which are absent in the directed graph setting. In a different direction the work of Nanongkai, Saranurak, and Yingchareonthawornchai [nsy19] and follow up improvements by Forster [fnsyy], developed fast algorithms for global connectivity based on local connectivity and randomization. At a highlevel they use sampling to identify two vertices on the opposite sides of a cut and then reduce to cut, or they use a localconnectivity algorithm from each vertex . This approach is particularly wellsuited for small connectivity.
For directed graph edge connectivity Gabow’s algorithm with running time is very good. In order to beat in the worst case, the bottleneck is the dense graph regime with high connectivity. We have two main ideas that are particularly well suited to this regime. First, we focus on the rooted case even though it may appear to be more difficult than the global connectivity case. The global connectivity can be much smaller than the rooted connectivity; for instance the graph may not be strongly connected, in which case the global edge connectivity is , while the rooted connectivity for a particular root can still be . Consider rooted connectivity from a given vertex . In order to reduce to cut we would like to find a node such that is the sink side of a minimum cut. Let be a sink side of a minimum cut and hence ; here denotes the set of edges entering . If is large we can randomly sample a small number of vertices and we will succeed with good probability in finding a vertex from . Therefore the difficult case is when is small and this is the setting in which we make our key observation: if the graph is simple (or edge capacities are small) and the sink side of a minimum cut is small (but not a singleton!), then cannot have a highdegree vertex. How can we take advantage of this? Since we are working with the rooted problem, we can shrink all highdegree vertices into the root ! In other words we can sparsify the graph if the sink side is small and compensate for the higher sampling rate (and larger number of cut computations) we need to find a vertex on the sink side. Simple in retrospect, this tradeoff between sparsification and sampling rate coupled with guessing the size of the sink component gives us the overall algorithm with some additional technical work. We believe that our highlevel idea will find use in other contexts when combined with other techniques.
Recent related work.
A recent and independent work of [li+21] has obtained an time algorithm for vertex connectivity in directed and unweighted graphs. We have not yet had time to digest and make a proper comparison to [li+21].
Recent followup work by one of the authors has extended the ideas in this work to obtain approximation algorithms for weighted graphs, for rooted and global, edge and vertex connectivity, with running times [quanrudapxcuts].
2 Edge connectivity
edgeconnectivity
edgeoverview
In this section, we prove the main theorem for edge connectivity, main. To this end, we will first introduce the main key lemma, called the Rooted Sparsification Lemma, in overviewsparsification. In bucket, we give a lemma that applies the Rooted Sparsification Lemma to give a faster algorithm when the number of vertices in the sink component is known to be in a fixed interval between and . main is then proven in mainproof, applying the ideas from bucket to each of a small family of intervals.
2.1 The Rooted Sparsification Lemma for Edge Connectivity
overviewsparsification edgesparsification
We introduce the key technical ingredient that we call the Rooted Sparsification Lemma. This lemma says that if the sink component of the minimum cut is small, then unless it is a singleton cut (which is easy to find directly), we can contract all vertices with high indegree into the root while preserving the minimum rooted cut exactly. The result is a smaller and sparser graph in which we can find the minimum rooted cut faster. Later we will see that the running time saved by operating on a smaller graph makes up for the difficulty in identifying a vertex from a smaller sink component.
[] simplesparsification Let . Consider the graph obtained by contracting all vertices with weighted indegree into . Let denote the contracted vertex in . Then we have the following.

is a multigraph with less than edges.

If the minimum number of vertices in a sink component of a minimum cut has greater than 1 and less than or equal to vertices, then the minimum cut and the minimum cut are the same.
Note that contraction cannot reduce the value of cut. An example illustrating the lemma is given in rootedsparsification. The proof is in two steps.
Small sinks make small cuts (except for singletons).
The first step towards the Rooted Sparsification Lemma for edge connectivity is the following basic observation relating the connectivity to the number of vertices in the sink component of a minimum rooted cut. For simple graphs (i.e., ), the following lemma says that except for the case where the minimum rooted cut is achieved by a singleton, the rooted connectivity is less than the number of vertices in the sink component of the cut. With capacities between and , we obtain a similar inequality except scaled by . See smallsinksmalledgecut for an illustration of the following lemma.
[] smallsinksmallcut Let be the minimum number of vertices in a sink component of a minimum cut. Then either or .
.
Let be the set of vertices on the sinkside of a cut with edges. Suppose . Every vertex in has weighted indegree . Consider all edges with head in . Because has capacities between and , of all the edges with head in , at most total weight have their tail in as well. Thus Rearranging, we have hence . ∎
The above argument is simple and (unsurprisingly) we realized that a similar line of reasoning has appeared in previous work [mansourschieber] (though towards a different algorithmic approach and not in the context of rooted connectivity).
Small sinks are sparse sinks.
We now prove the Rooted Sparsification Lemma, simplesparsification. The high level argument is very simple and we first give an informal argument to emphasize the intuition. If the sink component of the minimum cut is small, then by smallsinksmallcut, the minimum cut is also small. Suppose for the sake of discussion that the graph is simple (i.e., ). If both the minimum cut and the sink component are small and the graph is simple, then every vertex in the sink component has small indegree. The contrapositive implies that every high indegree vertex is on the source side of the cut. Thus the high indegree vertices can be safely contracted into the root.
Proof of the rooted sparsification lemma.
Recalling the statement of the lemma, it is easy to see that contracting all vertices with weighted indegree into results in a multigraph in which every vertex has weighted indegree , and hence there are at most edges total.
Let be the sink component of a minimum cut. Observe that contracting into cannot decrease the edge connectivity. If one can show that no vertices in are contracted into , then is the sink component of a minimum cut as well.
By smallsinksmallcut, the minimum cut has size . Because is simple and has vertices, every vertex in has indegree less than . Thus any contracted vertex is outside of . This completes the proof. ∎
2.2 Rooted connectivity for a fixed range of component sizes
bucket
Applying the Rooted Sparsification Lemma usefully requires a fairly tight upper bound on the number of vertices in the sink component of the minimum cut. In this section, we assume we are given a lower bound and an upper bound on the number of vertices in the sink component, and develop algorithms for the minimum rooted cut in this parametrized regime. The running times are decreasing in and increasing in ; that is, they are better for tighter bounds on the number of vertices in the sink component.
knowncomponentsize Let with . Suppose the sink component of the minimum cut has between and vertices. Then the minimum cut can be computed with constant probability in
Proof.
We first consider the case . By simplesparsification, we can reduce the number of edges to while preserving the cut and retaining all or more vertices in the sinkside component. Let us sample sink vertices in the remaining graph uniformly at random, and compute the minimum cut for each. This takes time for each instance, as desired. With constant probability, at least one sink is sampled out of the sink component of the minimum cut, which will return the minimum cut.
If , then we must also address the possibility of a singleton cut. We apply the above for and compare the output to all of the singleton cuts, and output the smallest of these cuts. ∎
2.3 Rooted connectivity for small sink components
ecsmallsink Let be a given parameter. There is a deterministic algorithm that runs in time and returns an cut with the following guarantee. If the sink component of a minimum cut has at most vertices, then the algorithm will return a minimum cut.
Proof.
If the sink side of the minimum cut has less than vertices, then via smallsinksmallcut, either a singleton induces a minimum cut, or the minimum cut has size . For the latter case, we apply the rooted sparsification lemma and reduce the graph to edges while preserving the minimum cut. We apply Gabow’s algorithm [gabow] to the sparsified graph and it runs time, and either finds a minimum rooted cut or certifies that the cut value in the sparsified graph has value . We compare the output with all singleton cuts. ∎
2.4 Algorithm for rooted edge connectivity
mainproof We now prove the main theorem for edge connectivity, main. By knowncomponentsize, if the number of vertices in the sink component is known, then we can reduce very efficiently to connectivity by either sparsifying the graph (if the number is small) or easily guessing a sink (if the number is large). More generally, we can pursue both strategies relative to any given upper and lower bounds on the number of vertices in the sink component. Meanwhile, for small component sizes (that are not singletons), we can still sparsify the graph, while the cut size must be small, which combine to produce fast running times via [gabow] in ecsmallsink. The only unknown is the number of vertices in the sink component. Here we guess the number of vertices up to a constant factor, which only requires enumerating a logarithmic number of guesses. We restate main for the sake of convenience.
See 1
Proof.
Let be a parameter to be determined. The sink component of the minimum cut either (a) is a singleton, (b) has at most vertices, or (c) has between and vertices for some . For each of these categories we apply a subroutine and take the minimum of the cut values found.
Singleton cuts are easy to evaluate in time. Let and . For , let . Let . For (b) we invoke ecsmallsink with maximum sink component . To address (c), for each , we invoke knowncomponentsize times with lower bound and upper bound on the number of vertices in the sink component. We use [brand++]. The combined running time is For , this gives the claimed running time. ∎
3 Rooted and global vertex connectivity
In this section, we describe and analyze the approximation algorithms for rooted and global vertex connectivity. The highlevel approach is similar to the previously discussed algorithm for edge connectivity. The first step, vertexsparsification, is a variant of the Rooted Sparsification Lemma that applies to (approximate) vertex connectivity. It plays a similar role as its counterpart for edge connectivity, allowing one to sparsify the graph when the sink component of the minimum rooted vertex cut is small. The proof of vertexsparsification is given vertexsparsification. We then give an algorithm specific to (roughly) the number of vertices in the sink component in parametrizedvertexcut. We use this algorithm as a subroutine in the final algorithm for approximate rooted connectivity in rootedvc. In globalvertexconnectivity, we give the reduction from approximate global vertex connectivity to approximate rooted vertex connectivity. The exact global vertex connectivity algorithm for integer weights follows from an appropriate choice of error parameter.
3.1 Rooted sparsification for approximate vertex connectivity
vertexsparsification
Recall that a key idea in the algorithm for (rooted) edge connectivity was the Rooted Sparsification Lemma, which allows us to substantially decrease the number of edges when the sink component of the minimum rooted cut is small. Underlying the rooted sparsification lemma for edge connectivity was a direct relation between the size of the sink component and the weight of the minimum edge cut — smallsinksmallcut in edgesparsification. But this relation does not hold for vertex connectivity, even in unweighted and undirected graphs – even if the sink component is small, the vertex incut can be very large. For example, for arbitrarily large and any fixed constant , let be a clique of size and let be a clique of size . Add edges between all and all . Let be an additional root vertex connected to every vertex in . Then is the sink component of the minimum vertex cut. It has a constant number of vertices, , while the size of the vertex cut, , is arbitrarily large.
That said, we show that a useful sparsification is possible if we relax to approximating the rooted vertex connectivity, and qualify the lemma by the assumption that no singleton cut already represents a good approximation. To this end, let . We say that is an inneighbor of if . We denote the set of inneighbors of a vertex by The definition of inneighbors naturally extends to sets of vertices; for we define . The weighted indegree of is defined as the total weight of all inneighbors of . Similarly we define the set of outneighbors of a vertex , denoted , as and the weighted outdegree of , denoted , as the sum of weights over .
Our first lemma gives an approximate relationship between the weight of the minimum weight rooted vertex cut and the weight of the sink component of the minimum weight rooted vertex cut.
[] Let be fixed. smallsinksmallvertexcut Suppose the inneighborhood of every nonroot vertex has total weight greater tha . Then the minimum vertex cut has more than weight in the sink component.
Proof.
Let the minimum cut be of the form , where . To prove the claim it suffices to show that .
For any vertex , by assumption, total weight of inneighbors is more tha . At most weight of these inneighbors are in the minimum vertex cut, . This implies that has more than weight of inneighors in , and hence (where the extra is for the weight of ). ∎
[] vertexsparsification Let be fixed. Let . Consider the graph obtained by replacing, for each vertex with weighted indegree , all of the incoming edges to with a single edge from to . Then we have the following.

has maximum weighted indegree at most .

has at most edges.

If the sink component of a minimum vertex cut in has weight , then the minimum vertex cut in and are the same.
Proof.
Let be the sink component of a minimum rooted vertex cut, of minimum weight among such sink components. Suppose has weight less than or equal to . By smallsinksmallvertexcut, . Therefore any vertex with weighted indegree greater than cannot be in of the minimum rooted vertex cut. We claim that replacing the incoming edges to does not decrease rooted vertex connectivities for . As a thought experiment, suppose we make the replacement over two steps, where we first add the edge from to , and then remove the other incoming edges to . The first step does not decrease vertex connectivities, and forces the rooted vertex connectivity from to to be . Removing the other incoming edges to does not effect the connectivity from to , so no other vertex connectivities from are effected either. Over the two steps, then, we see that no rooted connectivities from decrease.
On the other hand, since is not in the sink of the minimum vertex cut, the rooted vertex connectivity of does not change. ∎
3.2 Rooted vertex connectivity parametrized by sink component size
parametrizedvertexcut
We now give an algorithm for rooted vertex connectivity parametrized by the weight of the vertices in the sink component of the minimum rooted cut. More precisely, we take as additional input two weights and assume the sink component has weight between and .
In the following, let be the running time for vertex cut.
fixedsinksizevertexcut Let be fixed. Let be the total weight in the graph. Let with . Suppose also that the sink component of the minimum cut has between and total weight. Then the minimum cut can be computed with constant probability in
randomized time.
Proof.
By vertexsparsification, in time, we can reduce the number of edges to at most without decreasing the rooted vertex connectivity. We sample vertices from . Note that has weight at most .
We sample vertices independently in proportion to their weight. For each sampled vertex , we compute the minimum vertex cut in the sparsified graph. With constant probability, one of these vertices is in the sink component of the minimum vertex cut, and the minimum vertex cut is the minimum vertex cut. ∎
The simple observation that the weight of is at least is from [ghr].
3.3 Rooted vertex connectivity for small sink components
This section develops an approximation algorithm for rooted vertex connectivity specifically for the case where the sink component has small weight. The algorithm takes an upper bound on the weight of the sink component, and guarantees an approximate minimum cut when there is a minimum rooted vertex cut where the sink component has weight at most . The approach is inspired by the recent local connectivity algorithm of [fnsyy], and also integrates the rooted sparsification lemma. This algorithm is developed in two steps. The first step is a local cut algorithm that, given a vertex , searches for a small cut around in time proportional to a given upper bound on the weight of the sink component. The second step first applies the rooted sparsification lemma, finds a vertex in the sink component by random sampling, and runs the local cut algorithm for this choice of .
The following lemma, which describes the local cut algorithm, is nearly identical to [fnsyy] except for two small modifications. First, we work with integral capacities, which does not change any arguments. Second is the inclusion of the root which we want to keep on the opposite side of the local cut. The proof is included for the sake of completeness. In the following, the involume of a set of vertices in a directed, edgecapacitated graph is the sum of weighted indegrees over all vertices in . Similarly the outvolume is defined as the sum of weighted outdegrees.
rootedlocalcut Let be a directed graph with integral edge capacities. We assume that is already available in memory in adjacency list format. Let , and let be given parameters. Then there is a randomized algorithm that runs in time with the following guarantee.
Let be the minimum capacity of all cuts where the sink component has involume at most . If , then with constant probability, the algorithm returns an cut of capacity at most .
Proof.
Let be the sink component of a minimum edge cut among those where the sink component has involume at most . We run a randomized variation of augmenting paths in the reversed graph where is the source. Note that now has outvolume at most in . We run the following subroutine for at most iterations, where each iteration routes one unit of flow from to some chosen .
Each iteration runs DFS from in the residual graph, until it either (a) visits , (b) has traversed edges of total capacity at least , or (c) has explored all the edges reachable from while failing to satisfy either (a) or (b). In event (a), we route one unit of flow to . In event (b), we select one of the visited edges randomly in proportion to their capacity, and route one unit of flow to the endpoint of that edge. In either case, after routing, we update the residual graph by reverse (one unit of capacity) of each edge on the path from to the selected sink. In event (c), we return the entire component of vertices reachable from which induces an cut in the original graph. If, after iterations, we never reach event (c), then the algorithm terminates with failure.
We first argue that we return a approximate cut with constant probability. We first point out that the total outvolume of in the residual graph never increases, as we are reversing edges along edges along a path starting from . Next, we observe that in each instance of event (b), where we randomly sample the endpoint of a visited edge as a sink, there is less than probability that this endpoint lies in . This is because the graph search has traversed a total capacity of at least , and has outvolume at most . That is, the outvolume of represents at most an fraction of the searched edges.
Now, over the first iterations, we expect to sample less than sinks from . By Markov’s inequality, we sample less than sinks from over the first iterations with probability at least . In this event, if the algorithm did not find an cut within the first iterations, then we must have routed more than units of flow out of – a contradiction. Thus the algorithm finds an cut within iterations with probability at least . Since this cut was obtained as the reachable set of after routing at most units of flow, the cut has capacity .
It remains to prove the running time. Each iteration takes time to traverse at most edges. The algorithm runs for at most iterations. ∎
The next lemma presents the approximate rooted vertex cut algorithm that uses rootedlocalcut as a subroutine. It also uses the rooted sparsification lemma to reduce the size of the graph and give stronger bounds on the volume of the sink component of the desired vertex cut.
vcsmallsink Let be fixed. Let and suppose that the sink component of the minimum cut has weight . Then a approximate minimum cut can be computed with high probability in randomized time.
Proof.
By smallsinksmallvertexcut, either a approximate minimum cut is induced by a singleton, or the minimum vertex cut has weight at most . The former is addressed by inspecting all singleton cuts. For the rest of the proof, let us assume the latter. By vertexsparsification, we can sparsify the graph to have maximum weighted indegree , hence at most total edges.
Let be the sink component of the minimum cut, which has total vertex weight at most , and induces an cut with capacity . Recall the standard auxiliary “splitgraph” where vertex capacities are modeled as edge capacities. The highlevel idea is to find a vertex by random sampling and then apply rootedlocalcut to the appropriate auxiliary vertices of and in the split graph.
To this end, we first bound the volume of the sinkcomponent corresponding to in the splitgraph. We recall that the split graph splits each vertex into an auxiliary “invertex” and an auxiliary “outvertex” . For each there is a new edge with capacity equal to the vertex capacity of . Each edge is replaced with an edge with capacity^{3}^{3}3Usually, this edge is set to capacity , but either the weight of or the weight of are also valid. equal to the vertex capacity of . As a sink component, maps to a vertex set in the splitgraph consisting of (a) both copies and of each vertex , and (b) the outvertex of each vertex in the vertex incut . For each vertex , has (edge)weighted indegree equal to the vertexweighted indegree of in the original graph, which is at most . This sums to over all . For each , has weighted indegree equal to the vertex weight of , which sums to the total vertex weight of . Lastly, for each , has weighted indegree equal to the vertex weight of . This sums to over all . All summed up, the total involume of in the splitgraph is at most times the total vertex weight of .
Suppose we had a constant factor estimate
for the total vertex weight of . Then we can sample vertices by weight from . With high probability, we sample vertices from . For each sampled vertex we invoke rootedlocalcut to find an cut, with upper bound on the volume of the sink component and as the upper bound on the cut. With high probability, one of these calls returns a approximate cut. The total time, over all calls, would be .Of course, we do not know the vertex weight of a priori. However, we know that it is upper bounded by , and let enumerate all powers of 2 between and . For each , run the process described above under the hypothesis that is a constant factor estimate for the total vertex weight of . Each choice of takes time. There are choices of . One of these choices of is a constant factor for the total volume of and produces a approximate minimum cut with high probability. ∎
3.4 Rooted vertex connectivity
rootedvc
We now present the algorithm for approximate rooted vertex connectivity and prove simplevcrooted. The algorithm combines the subroutine in fixedsinksizevertexcut for logarithmically many ranges of weights, and vcsmallsink for sufficiently small weights. We restate simplevcrooted for the sake of convenience.
See 1
Proof.
Let . Let , and let For each , let . Let where we recall that is the weighted outdegree of . For each , we apply fixedsinksizevertexcut with lower bound and upper bound on the weight of the sink component of the minimum vertex cut. We repeat this subroutine times for each to amplify the success probability from constant to high probability. We use [brand+]. We also apply vcsmallsink with has an upper bound on the sink component size. The set of all cuts obtained by these methods includes a approximate minimum cut with high probability, and we return the minimum of these cuts. The combined running time is
as desired. The exact bound follows by first using the approximation algorithm to obtain a constant factor estimate for , and then setting setting . ∎
3.5 Global vertex connectivity
globalvertexconnectivity
We now shift to global vertex connectivity and prove simplevcglobal, which we address by reduction to the algorithm for rooted vertex connectivity above. We note that obtaining a root is slightly nontrivial because many vertices may be in the minimum weight vertex cut. We restate simplevcglobal for the sake of convenience.
See 1
Proof.
Let denote the global vertex connectivity. If we sample a single vertex in proportion to its weight, then with probability , is not in the minimum vertex cut. Then either the rooted vertex connectivity from , or to (i.e., from in the graph with all the edges reversed), will give the rooted vertex cut. In principle we would like to apply rootedvcreduction with root in both orientations, which conditional on not being in the minimum cut, succeeds with high probability. We amplify by repeating times to obtain the high probability bound. Observe that the running time, via rootedvcreduction, is
We would like to remove the factor.
To this end, observe that the term arises from applying the rooted sparsification lemma for various estimates of the weight of the sink component. Recall that for fixed and , the sparsification lemma replaces, for every vertex with indegree , all the incoming edges to with a single edge from the root. Note that much of the sparsification lemma can be executed without . In particular, we can remove all incoming edges to the high indegree vertices without knowing ; once is given, we add an edge from to each of these vertices. The key point is that the first part, which takes time, can be done once for all sampled roots for each value of . Thereafter, each of the roots takes to complete the sparsification for that root. This replaces the term with , which is dominated by .
For the exact algorithm, we first apply the approximation algorithm with obtain a factor2 approximation to within the claimed running time. We then apply the approximation algorithm again with . ∎
Comments
There are no comments yet.