1 Introduction
Although the term “big data” has been overused in recent years, there is a factual trend in growing input sizes for computational tasks. In practical applications, this has led to many engineering and architectural efforts for designing scalable systems [DG04, Whi12, IBY07, ZCF10]
. In theory of computing, this trend has mainly been reflected by studying models that penalize reading, storing, or exchanging data such as the property testing model
[GGR98], the streaming model [HRR98, McG14], the CONGEST model [Pel00], the congested clique model [LPPP05], the massively parallel computation model [KSV10], or the machine model [KNPR15]. A recent take on this are Local Computation Algorithms [RTVX11, LM17], where the goal is to design sublineartime algorithms that do not even need to read the whole input.In this paper, we study a natural “local” version of the problem of finding an edge cut of bounded size with applications to higher connectivity: given a starting vertex , detect a “small” component containing with at most outgoing edges (if it exists). This problem has implicitly been studied before in the context of property testing [GR02, OR11] and for developing a centralized algorithm that computes the maximal edge connected subgraphs of a directed graph [CHI17]. Recently, a variant for vertex cuts has been studied for obtaining faster vertex connectivity algorithms [NSY19]. A somewhat similar problem of locally detecting a small component with lowconductance has recently been studied extensively [KT19, HRW17, SW19], in particular to obtain centralized algorithms for deterministically computing the edge connectivity of an undirected graph.
We improve upon the query complexity and running time of all prior local computation algorithms for detecting boundedsize cuts. The significance of this contribution is confirmed by the fact that it almost readily implies faster algorithms for several problems in higher connectivity. First, we obtain the first nearlylinear time algorithm for computing the vertex connectivity of a directed or undirected graph whenever is polylogarithmic in the number of vertices. Our algorithm is the fastest known algorithm for a wide, polynomial, range of . Second, we obtain algorithms for computing the maximal edge connected subgraphs of directed or undirected graphs that significantly improve the algorithms of Chechik et al. [CHI17]. Third, we improve upon the state of the art in property testing algorithms for higher connectivity in essentially all settings, considering both edge connectivity and vertex connectivity, both directed and undirected graphs, and both graphs of bounded and unbounded degree. Furthermore, we give a much more uniform treatment of all these settings. In particular, our improvements answer two longstanding open problems in the field posed by Goldreich and Ron [GR02] and by Orenstein and Ron [OR11], respectively.
We next settle our notation and terminology in Section 1.1 before we discuss our results and compare them with related work in Section 1.2. We then proceed by giving the details of our results: the local cut detection result in Section 2, the vertex connectivity result in Section 3, the result on computing the maximal edge connected subgraphs in Section 4, and the property testing results in Section 5. Finally, we conclude the paper in Section 6 with some open problems.
1.1 Preliminaries
In the following we fix our terminology and give all relevant definitions.
Graph Terminology
In this paper, we consider input graphs with vertices and edges . Graphs might be directed, i.e., , or undirected, i.e., . For any two subsets of vertices and we define the set of edges going from to as . Note that in undirected graphs. In directed graphs, we say that an edge is reachable from a vertex if is reachable from . The reverse of an edge is the edge and the reverse of a graph is the graph in which every edge is reversed, i.e., with edge set
. We say that an event occurs with high probability if it does so with probability at least
for any (fixed) choice of the constant .A graph is strongly connected if for every pair of vertices and there is a path from to and a path from to . (The former implies the latter in undirected graphs and we usually just call the graph connected in that case.) A graph is edge connected if it is strongly connected whenever fewer than edges are removed. A graph is vertex connected if it has more than vertices and is strongly connected whenever fewer than vertices (and their incident edges) are removed. The edge connectivity of a graph is the minimum value of such that the graph is edge connected and the vertex connectivity is the minimum value of such that the graph is vertex connected. An edge cut is a partition of the vertices into two nonempty sets and . The size of an edge cut is the number of edges going from to , i.e., . A vertex cut is a partition of the vertices into three sets , , and such that and are nonempty and there are no edges from to , i.e., . The size of a vertex cut is , the size of . Observe that a graph is edge connected if and only if it has no edge cut of size at most and it is vertex connected if and only if it has no vertex cut of size at most .
In our paper, we are mainly interested in detecting socalled edgeout and in components and vertexout and in components, which we define in the following. For every subset of vertices , the vertex size of is , the edge size of is , the volume of is , and the symmetric volume of is .
Definition 1.1.
A edgeout (in) component of a directed graph is a nonempty subset of vertices such that there are at most edges leaving (entering) , i.e., (). is minimal if for every proper subset of the number of edges leaving (entering) is more than the number of edges leaving (entering) . is proper if is a proper subset of , i.e., .
Observe that for every proper, nonempty edgeout component there exists an edge cut of size at most , certifying an edge connectivity of less than , and for every proper, nonempty edgein component there exists an edge cut of size at most , certifying a vertex connectivity of less than .
Definition 1.2.
A vertexout (in) component of a directed graph is a nonempty subset of vertices such that the number of vertices reached from edges leaving (entering) is at most , i.e., for (). is minimal if for every proper subset of the number of vertices reached from edges leaving (entering) is more than the number of vertices reached from edges leaving (entering) . is proper if is a proper subset of , i.e., .
Observe that for every proper, nonempty vertexout component there exists a vertex cut of size at most and for every proper, nonempty vertexin component there exists an edge cut of size at most .
In this paper, we use notation to suppress polylogarithmic factors.
Query Model
In the incidencelists model, we assume that there is some order on the outgoing as well as on the incoming edges of every vertex. In directed graphs, the algorithm can, for any vertex and any integer , in a single query ask for the th outgoing edge of (and either get this edge in return or a special symbol like if has fewer than outgoing edges). Similarly, the algorithm can ask for th incoming edge of . In undirected graphs, the algorithm can simply ask for the th edge incident on . The query complexity of an algorithm is the number of queries it performs.
Property Testing
Informally, the main goal in property testing is to find out whether a given graph, to which the algorithm has query access, has a certain property by performing a sublinear number of queries, allowing a “soft” decision margin. In this paper, we consider the properties of being edge connected or being vertex connected.
Formally, a graph property is a subset of graphs closed under isomorphism, usually specified implicitly by a predicate . In the boundeddegree model a graph is said to be far from having the property in question, if more than edge modifications must be made to obtain a graph that has the property. In directed graphs, is a given upper bound on the maximum in or outdegree of any vertex (i.e., the maximum number of incoming or outgoing edges of any vertex). In undirected graphs, is a given upper bound on the maximum degree of any vertex (i.e., the maximum number of edges incident on any vertex). Note that is an upper bound on in directed graphs and an upper bound on in undirected graphs. In the unboundeddegree model, the number of edge modifications must be more than , where . Note that is an upper bound on in directed graphs and an upper bound on in undirected graphs.
A property testing algorithm has query access to the input graph and, with probability at least , is required to accept every graph that has the property and reject every graph that is far from having the property. We assume that the property testing algorithm knows and or , respectively, in advance and that and are given as parameters.
1.2 Discussion of Our Results
In the following we compare our results with prior work.
1.2.1 Local Cut Detection
Consider the following “local” problem: We are given a starting vertex and need to detect whether there is a edgeout component containing of vertex size at most (or of edge size at most ) in . The goal is to design sublineartime algorithms that only have query access to the graph and thus answer this question by locally exploring the neighborhood of instead of reading the whole graph. Several algorithms for this problem have been proposed in the literature. We review them in the following and compare them to our new result.
In undirected graphs, a local variant of Karger’s minimum cut algorithm [Kar00] gives the following guarantees.
Theorem 1.3 (Implicit in [Gr02]).
There is a randomized algorithm that, given integer parameters and , a starting vertex , and query access to an undirected graph , with queries detects, with constant success probability, whether there is a edgeout component containing of vertex size at most and edge size at most in and if so returns such a component.
In directed graphs, a backtracking approach that tries to identify the at most edges leaving the component gives the following guarantees.
Theorem 1.4 ([Or11]).
There is a deterministic algorithm that, given integer parameters and , a starting vertex , and query access to a directed graph , with queries in general and with in graphs of maximum degree detects whether there is a edgeout component containing of vertex size at most in and if so returns such a component.
With a different motivation – computing the edge connected components of a directed graph – Chechik et al. [CHI17] developed a faster local cutdetection procedure for directed graphs. The guarantees on the detected component are a bit weaker than those of Orenstein and Ron [OR11] as the component detected by the algorithm might be larger than . In the applications considered in this paper, this however is not an issue; as long as one is willing to pay the overhead in the complexity for detecting the component, the algorithms can also rely on the weaker guarantee.
Theorem 1.5 ([Chi17]).
There is a deterministic algorithm that, given integer parameters and , a starting vertex , and query access to a directed graph , with queries returns a set of vertices such that (1) if there is a edgeout component containing of edge size at most , then and (2) if , then is a minimal edgeout component containing of edge size at most .
Our approach is to follow the general algorithmic framework of Chechik et al. and to speed it up by using randomization. In this way we reduce the dependence on in the query complexity from exponential to polynomial. Formally, we achieve the following guarantees.
Theorem 1.6.
There is a randomized algorithm that, given integer parameters and , a probability parameter , a starting vertex , and query access to a directed graph , with queries returns a set of vertices such that (1) if there is a edgeout component containing of edge size at most in , then with probability at least and (2) if , then is a minimal edgeout component of edge size at most in . If every query to the graph can be performed in expected constant time, then the running time of the algorithm is .
We give a very general reduction that immediately makes this improvement carry over to detecting vertex cuts with the following guarantees.
Theorem 1.7.
There is a randomized algorithm that, given integer parameters and , a probability parameter , a starting vertex , and query access to a directed graph , with queries returns a set of vertices such that (1) if there is a vertexout component containing of (symmetric) volume at most in , then with probability at least and (2) if , then is a vertexout component of (symmetric) volume at most in . If every query to the graph can be performed in expected constant time, then the running time of the algorithm is .
This problem for vertex cuts has recently been studied by Nanongkai, Saranurak, and Yingchareonthawornchai [NSY19] in the context of computing the global vertex connectivity. They get the following guarantees.
Theorem 1.8 ([Nsy19]).
There is a deterministic algorithm that, given integer parameters and , a starting vertex , and a directed graph in adjacencylist representation, in time returns a set of vertices such that (1) if there is a vertexout component containing of volume at most in , then with probability at least and (2) if , then is a vertexout component of volume at most in .
We remark that Nanongkai, Saranurak, and Yingchareonthawornchai also study an approximate version of this problem where the size of the vertex cut may exceed by a factor of .
1.2.2 Computing the Vertex Connectivity
Computing the vertex connectivity of graph is a classic problem in graph algorithms. Despite numerous research efforts, the conjectured lineartime algorithm [AHU74] has not yet been found. In fact, even if is constant, no nearlylinear time algorithm has been given in the literature to date. We give the first algorithm providing this guarantee.
For a long time, the state of the art was either a running time of due to Henzinger, Rao, and Gabow [HRG00], or a running time of due to Cheriyan and Reif [CR94], where is the matrixmultiplication exponent for which currently [Gal14] is known. In undirected graphs, the state of the art was either a running time of due to Henzinger, Rao, and Gabow [HRG00] or a running time of due to Linial, Lovász and Wigderson [LLW88]. Very recently, Nanongkai, Saranurak, and Yingchareonthawornchai [NSY19] improved upon some of these bounds by giving an algorithm with running time in directed graphs and an algorithm with running time in undirected graphs. All of these algorithms are deterministic. The fastest known deterministic algorithm by Gabow [Gab06] has a running time of in directed graphs and a running time of in undirected graphs. See [NSY19] for a more thorough overview of prior work. We significantly improve upon this state of the art, by giving an algorithm with running time in directed graphs and an algorithm with running time in undirected graphs. Our algorithms are randomized MonteCarlo algorithms that are correct with high probability. Table 1 gives an overview over all of these results.
Graph class  Running time  Deterministic  Reference 
directed  yes  [Gab06]  
directed  no  [HRG00]  
directed  no  [CR94]  
directed  no  [NSY19]  
directed  no  here  
undirected  yes  [Gab06]  
undirected  no  [HRG00]  
undirected  no  [LLW88]  
undirected  no  [NSY19]  
undirected  no  here 
Our algorithms are the first to run in nearly linear time for a wide range of values of (whenever is polylogarithmic in ). Furthermore, in undirected graphs we give the current fastest solution as long as , i.e., roughly when . In directed graphs, the precise number depends on the density of the graph, but in any case we do give the fastest solution as long as , i.e., roughly when .
1.2.3 Computing the Maximal Edge Connected Subgraphs
For a set of vertices, its induced subgraph is a maximal edge connected subgraph of if is edge connected and no superset of has this property. The problem of computing all maximal edge connected subgraphs of is a natural generalization of computing strongly connected components to higher edge connectivity.
For a long time, the state of the art for this problem was a running time of for and for . The first improvement upon this was given by Henzinger, Krinninger, and Loitzenbauer with a running of for and for . The second improvement was given by Chechik et al. [CHI17] with a running time of for and for . In undirected graphs, a version of the algorithm by Chechik et al. runs in time for and in time for . In this paper, we improve upon this by designing an algorithm that has expected running time , reducing the dependence on from exponential to polynomial. We furthermore improve the running time for undirected graphs to thus improving both the dependence on and on . Table 2 compares our results to previous results.
Parameter  Graph class  Running time  Deterministic  Reference 
directed  yes  implied by [GT85]  
directed  yes  implied by [Gab95]  
directed  yes  [HKL15]  
directed  yes  [HKL15]  
directed  yes  [CHI17]  
directed  yes  [CHI17]  
undirected  yes  [CHI17]  
undirected  yes  [CHI17]  
directed  no  here  
undirected  no  here 
Note that another natural way of generalizing the concept of strongly connected components to higher edge connectivity is the following: A edge connected component is a maximal subset of vertices such that any pair of distinct vertices is edge connected in .^{1}^{1}1Note that the edge disjoint paths between a pair of vertices in a edge connected component might use edges that are not contained in the edge connected component. This is not allowed for maximal connected subgraphs. For a summary on the state of the art for computing the maximal edge connected subgraphs and components in both directed and undirected graphs, as well as the respective counterparts for vertex connectivity, we refer to [CHI17] and the references therein.
1.2.4 Property Testing for Higher Connectivity
After the seminal work of Goldreich and Ron [GR02], property testing algorithms for connectivity have been studied for various settings. Table 3 shows the state of the art in the unboundeddegree model and compares it with our results, whereas Table 4 shows the state of the art in the boundeddegree model and compares it with our results. Observe that we subsume all prior results. In particular, we solve the open problem of Goldreich and Ron [GR02] asking for a faster property testing algorithm for edge connectivity in undirected graphs of boundeddegree. Furthermore, we solve the open problem of Orenstein and Ron [OR11] asking for faster property testing algorithms for edge connectivity and vertex connectivity with polynomial dependence on in the query complexity.
State of the art  Here  

undirected edge connectivity  [PR02]  
directed edge connectivity  [YI10, OR11]  
undirected vertex connectivity  [OR11]  
directed vertex connectivity  [OR11] 
State of the art  Here  

undirected edge connectivity  [GR02]  
undirected edge connectivity  [GR02]  
undirected edge connectivity  [GR02]  
directed edge connectivity  [YI10]  
undirected vertex connectivity  [YI12]  
directed vertex connectivity  [OR11] 
Note that the query complexity of the edge connectivity tester for undirected boundeddegree graphs in Theorem 3.1 of [GR02] is stated as . However, to the best of our understanding, this bound only applies for connected graphs. Following Algorithm 3.18 in [GR02], the query complexity in arbitrary boundeddegree graphs should therefore be . While such a deviation is certainly marginal and often hidden with good reason in the notation, we do report it here to make clear that no further arguments than the combinatorial ones of Orenstein and Ron [OR11] and the algorithmic ones in this paper are needed to obtain the state of the art.
Independent Work
In followup work to [NSY19], Nanongkai, Saranurak, and Yingchareonthawornchai have independently claimed results with the same guarantees as ours for locally computing a boundedsize edge or vertex cut, for computing the vertex connectivity of a directed or an undirected graph, and for computing the maximal edge connected subgraphs of a directed graph [Sar19].
2 Local Cut Detection
In this section we first prove Theorem 1.6 by giving a fast local procedure for detecting a edgeout component of edge size at most . We then obtain an analogous statement for vertex connectivity.
2.1 Detecting BoundedSize Edge Cuts
We exploit that a edge out component has at most edgedisjoint paths leaving the component. Once we “block” these paths, we will not be able to leave the component in any other way and may conclude that the set of vertices reachable from is a edge out component. In particular, we try to find these paths in an iterative manner using only simple depthfirst searches (DFS). In principle, we can hope to keep each DFS “local” by exploring only the neighborhood of as the component has at most edges. However, since we do not know the component in advance, we do not know which vertices visited by each DFS are outside of the component. Our main idea is to perform each DFS up to a “budget” for processing edges and to then sample one of the processed edges uniformly at random.^{2}^{2}2We consider the variant of DFS using a stack in which the stack initially contains the starting vertex and in each iteration a vertex is popped from the stack and visited, which means that all its outgoing edges are processed by pushing their other endpoints on the stack. We add the path from to the tail of the sampled edge in the current DFS tree to our set of chosen paths. If there is a edgeout component containing of edge size at most , then there are only edges whose tails are inside the component. Thus, the endpoint of our new path is lying inside of the component with probability only . We repeat this process times, blocking the edges of the paths chosen so far in each DFS. Thus, the probability of one of the tails of a sampled edge lying inside of the component is at most by the union bound. In this way, we obtain paths leaving the component with constant probability and we can verify that an additional DFS not using one of these paths cannot reach more than the edges of the component. By a standard boosting approach we can increase the success probability at the cost of repeating this algorithm multiple times.
As described so far, this approach still has the problem that there might be no small edgeout component containing at all and the final DFS might simply fail to process more than edges because our choice of paths blocked some relevant edges. In particular, each of our chosen paths might leave and rerenter the component multiple times, as we only have a sufficiently high probability that the endpoint of the path is outside of the component. To avoid such a situation, we do not literally block the edges of the paths found so far by removing them from the graph. Instead, we use the augmenting paths framework of Chechik et al. [CHI17] that after each iteration reverses the edges of our chosen path, similar to residual graph constructions in maximum flow algorithms.
In more detail, our algorithm works as follows: First, we perform up to depthfirst searches up to a budget of edges. Consider the th DFS. If the DFS is completed before the budget on the number of edges is exceeded (i.e., if the DFS processes less than edges), we return the set of vertices found in the DFS as a edgeout component. Otherwise, we sample one edge processed by the DFS uniformly at random and let be the path from to the tail of this edge in the DFS tree. A special case arises if the edge is the reversal of the edge . If this happens, then we let be the path from to , the tail of the original edge in , in the DFS tree. We then reverse the edges on in the graph and start the next DFS. Finally, we perform another DFS up to a budget of edges. Again, if the DFS is completed before the budget on the number of edges is exceeded, we return the set of vertices found in the DFS as a edgeout component. Otherwise, we return the empty set to indicate that no outedge component of edge size at most has been found. The pseudocode of this procedure is given in Algorithm LABEL:alg:local_procedure.
algocf[htbp]
In the following, we prove Theorem 1.6 by a series of lemmas. We start with the following lemmas from Chechik et al. [CHI17]; we give the proofs for completeness using our own notation.
Lemma 2.1 ([Chi17]).
Let be a set of vertices containing and let . Assume that contains of the endpoints of the paths found in Procedure DetectComponent for some and any . Then in there are fewer edges from to than in .
Proof.
Consider the (multi)graph that is obtained from by contracting the vertices of to a single vertex and the vertices of to a single vertex . Applying the contraction to the paths , we obtain for each a set of edges between and that represents the contraction of , where we keep the direction of edges as in . Let and for let be the (multi)graph obtained from by reversing the edges of . Note that the graph can also be obtained from by contracting and , respectively. By definition, the graphs differ from only in the direction of the edges between and . Further we have that if ends at a vertex of (case 1), then in the number of edges from to is one more than the number of edges from to ; in contrast, if ends at a vertex of (case 2), then in there are as many edges from to as from to . In case 1 the number of edges from to in is one lower than in , while in case 2 the number of edges from to is the same in and . Let be the number of paths among that end in . We have that the number of edges from to in , and therefore the number of edges from to in , is equal to the number of paths from to in minus . ∎
Lemma 2.2 (Implicit in [Chi17]).
If Procedure DetectComponent returns for some , then is a minimal edgeout component containing in .
Proof.
Let be the set of vertices reachable from in and let be . Observe that the set is returned only if the th DFS has been completed without being stopped because of exceeding its “edge budget”. Therefore .
If , then is the set of vertices reachable from in , which trivially is a minimal edgeout component of containing . Consider now the case . By the definition of , contains and there are no edges from to in . Thus by Lemma 2.1 the number of edges from to in is equal to the number of paths among that end in . Thus, has outgoing edges in , i.e., is an edgeout component of . It remains to prove the minimality of , i.e., to show that does not contain a proper subset that contains and has or less outgoing edges. Assume by contradiction that such a set exists and let . By , at least of the paths among end in . Thus, by Lemma 2.1, there are no edges from to in . This implies that the set of vertices reachable from in is , contradicting the assumption that is this set. ∎
Lemma 2.3 (Implicit in [Chi17]).
Let be a minimal edgeout component containing of edge size at most and assume for each that at least edges are reachable from in and that ends in . Then Procedure DetectComponent returns .
Proof.
By definition, there are at most edges from to in . As by assumption, all paths end in , there are no edges from to in by Lemma 2.1. As contains and has edge size at most , the number of vertices reachable from in is at most . Thus, the DFS in Line LABEL:line:final_DFS of Procedure DetectComponent traverses all vertices reachable from in and a nonempty set containing at least is returned. ∎
Lemma 2.4.
Let be a minimal edgeout component containing of edge size at most and assume for each that at least edges are reachable from in . Then the probability that there is some such that ends in is at most .
Proof.
First, fix some . The th sampled edge is either contained in or its reverse edge is. In the first case ends in if and only if the tail of the is contained in and in the second case ends in if and only if the tail of the reverse of is contained in . As has edge size at most and there are at most edges leaving , there are at most edges of whose tail is contained in . By the assumption we have , i.e., was sampled from a set of distinct edges. Thus, the probability that ends in is at most . Now by the union bound, the probability that for least one the path ends in is at most . ∎
Lemma 2.5.
If Procedure DetectComponent returns , then is a minimal edgeout component of edge size at most in . If has a edgeout component containing of edge size at most , then Procedure DetectComponent returns with probability at least . The query complexity of Procedure DetectComponent is .
Proof.
To prove the correctness claims, observe first that is always reachable from itself and thus the only possibility for the procedure to return a set not containing is in Line LABEL:line:algorithm_returns_0 (where it returns ). Now the first correctness claim follows from Lemma 2.2 and the fact that all sets returned by the algorithm have edge size at most if and at most if . It remains to show that Line LABEL:line:algorithm_returns_0 is executed with probability at most . A precondition for this to happen is that for every the number of edges reachable from in is at least . Let be a edgeout component containing of edge size at most in . By Lemma 2.4 the probability that every path (for ) ends in is at most . If that is the case, then the procedure returns by Lemma 2.3. Thus, the probability of the procedure returning a set containing is at least .
To bound the query complexity, observe that the procedure performs at most one depthfirst search up to edges and depthfirst searches up to edges. Thus, the total number of queries is bounded by . ∎
Lemma 2.6.
If Procedure DetectComponentParam returns , then is a minimal edgeout component of edge size at most in . If has a edgeout component containing of edge size at most , then Procedure DetectComponentParam returns with probability at least . The query complexity of Procedure DetectComponentParam is .
Proof.
The first part of the lemma directly follows from the first part of Lemma 2.5. To prove the second part of the lemma, assume that has a edgeout component containing of edge size at most . The probability that a single call of Procedure DetectComponent returns a set not containing is at most by Lemma 2.5. Thus, the probability that independent calls of Procedure DetectComponent each return a set not containing is at most . It follows that the probability that DetectComponentParam returns a set containing is at least .
The bound on the query complexity and the running time directly follows from Lemma 2.5 ∎
We finally argue that Procedure DetectComponentParam can be implemented to run in time . In Procedure DetectComponent, we store all edges queried so far in hash tables, with one hash table per vertex containing its incident edges. Whenever we reverse the direction of some edge in Line LABEL:line:reverse_edges_on_path, we do so by replacing with in the hash tables of and . Recall that by assumption each query takes constant time in expectation and there are queries. As additionally each path has length and there are at most such paths for which the edges are reversed, the number of operations to the hash tables is . This gives an expected running time of for Procedure DetectComponent. By being a little more careful we can also get a worstcase bound by tolerating a slightly larger error probability: we stop the algorithm and return whenever its running time so far exceeds the expected bound by a factor of . By Markov’s bound this happens with probability at most . This decreases the probability of Procedure DetectComponent to return from to . We can account for this increase by increasing the number of repetitions in Line LABEL:line:repeat_procecdure of procedure DetectComponentParam from to . Thus, the running time of Procedure DetectComponentParam will be and Theorem 1.6 follows.
2.2 Detecting BoundedSize Vertex Cuts
In the following, we prove Theorem 1.7 by reducing local vertex cut detection to local edge cut detection. To do this, we modify a wellknown reduction that has previously been used for computing the local vertex connectivity of a pair of vertices by performing a maximum flow computation [Eve75].
Given a directed graph containing vertex , define the graph as follows:

For every vertex , contains two vertices and and additionally a vertex , i.e.,
where only and are identical.

For every vertex , gets all incoming edges of , gets all outgoing edges of , and there additionally is an edge from to , i.e.,
Note that we do not explicitly have to modify the input graph (to which we have query access) in algorithmic applications. Any algorithm running on can onthefly decide for each edge whether it is from the first set in or from the second set in . In the first case, the edge can be queried from , and in the second case the edge can be created by the algorithm instantly.
Let be a subset of edges in . Let be its set of boundary vertices. Recall that the symmetric volume of in is defined as
Let be a subset of edges in and let be its set of boundary vertices. Furthermore, define the interior of as and define the restricted symmetric volume of in as
We now present two lemmas that formally express the tight connections between vertexout components containing in and vertexout components containing in .
Lemma 2.7.
If there is a vertexout component containing in with (), then there is a edgeout component containing in with ().
Proof.
Let denote the at most boundary vertices of , i.e., those vertices with incoming edges from . Define as the component that is cut at the edges connecting to for the boundary vertices, i.e.,
Now let be an edge leaving in and suppose is of the form . Then , and, by the definition of , and , which contradicts the fact that contains all boundary vertices. Therefore, every edge leaving in must be of the form which, by the construction of is only possible for . Thus, there are at most edges leaving .
We now show that . The proof that would follow a similar, but simpler, argument. In particular, we will show that for every edge we either have for some or for some . It then follows that
as desired
Let and assume that for some for some . If , then by the definition of it must be the case that and therefore . Otherwise, we have . By the definition of , , and by the definition of , implies and thus . It follows that . ∎
Lemma 2.8.
Let be a minimal edgeout component containing in . Then is a vertexout component containing in with .
Proof.
In the proof we will use counting arguments that implicitly consider the onetoone mappings that map each vertex to the edge and each edge to the edge .
Let be the boundary vertices of . We will show that to every vertex we can uniquely assign one edge , which implies . As is a edgeout component we have
Comments
There are no comments yet.