next up previous contents index CD CD Algorithms
Next: Network Flow Up: Graph Problems: Polynomial-Time Previous: Eulerian Cycle / Chinese

Edge and Vertex Connectivity



Input description: A graph G. Optionally, a pair of vertices and t.

Problem description: What is the smallest subset of vertices (edges) whose deletion will disconnect G? Alternatively, what is the smallest subset of vertices (edges) that will separate from t?

Discussion: Graph connectivity often arises in problems related to network reliability.     In the context of telephone networks, the vertex connectivity is the smallest number of switching stations that a terrorist must bomb in order to separate the network, i.e. prevent two unbombed stations from talking to each other.   The edge connectivity is the smallest number of wires that need to be cut to accomplish the same thing. One well-placed bomb or snipping the right pair of cables suffices to disconnect the network above.

The edge (vertex) connectivity of a graph G is the smallest number of edge (vertex) deletions sufficient to disconnect G. There is a close relationship between the two quantities. The vertex connectivity is always no smaller than the edge connectivity, since deleting one vertex incident on each edge in a cut set succeeds in disconnecting the graph. Of course, smaller vertex subsets may be possible. The minimum vertex degree is an upper bound on both the edge and vertex connectivity, since deleting all its neighbors (or the edges to all its neighbors) disconnects the graph into one big and one single-vertex component.

Several connectivity problems prove to be of interest:

Both edge and vertex connectivity can be found using network flow techniques.   Network flow, discussed in Section gif, interprets a weighted graph as a network of pipes where the maximum capacity of an edge is its weight, and seeks to maximize the flow between two given vertices of the graph. The maximum flow between tex2html_wrap_inline29006 in G is exactly the weight of the smallest set of edges to disconnect G with tex2html_wrap_inline29008 and tex2html_wrap_inline29010 in different components. Thus the edge connectivity can be found by minimizing the flow between tex2html_wrap_inline29012 and each of the n-1 other vertices in an unweighted graph G. Why? After deleting the minimum-edge cut set, tex2html_wrap_inline29014 must be separated from some other vertex.

Vertex connectivity is characterized by Menger's theorem,   which states that a graph is k-connected if and only if every pair of vertices is joined by at least k vertex-disjoint paths. Network flow can again be used to perform this calculation, since in an unweighted graph G a flow of k between a pair of vertices implies k edge-disjoint paths.       We must construct a graph G' with the property that any set of edge-disjoint paths in G' corresponds to vertex-disjoint paths in G. This can be done by replacing each vertex tex2html_wrap_inline29020 of G with two vertices tex2html_wrap_inline29022 and tex2html_wrap_inline29024 , such that edge tex2html_wrap_inline29026 for all tex2html_wrap_inline29028 , and by replacing every edge tex2html_wrap_inline29030 by edges tex2html_wrap_inline29032 , tex2html_wrap_inline29034 in G'. Thus two edge-disjoint paths in G' correspond to vertex-disjoint paths in G, and as such, the minimum maximum-flow in G' gives the vertex connectivity of G.

Implementations: Combinatorica [Ski90] provides Mathematica implementations of edge and vertex connectivity, as well as connected, biconnected, and strongly connected components with bridges and articulation vertices. See Section gif.   

LEDA does not currently seem to have biconnected components and bridges, but it   does contain all the tools to implement connectivity algorithms, including network flow.

Pascal implementations of biconnected and strongly connected components appear in [MS91].   See Section gif for details.

The Stanford GraphBase (see Section gif) contains   routines to compute biconnected and strongly connected components.

Notes: Good expositions on the network-flow approach to edge and vertex connectivity include [Eve79a, Ski90]. The correctness of these algorithms is based on Menger's theorem [Men27] that the connectivity is determined by the number of edge and vertex disjoint paths separating a pair of vertices.   The maximum-flow, minimum-cut theorem is due to Ford and Fulkerson [FF62].

Efficient randomized algorithms for computing graph connectivity have recently been developed by Karger.   See Motwani and Raghavan [MR95] for an excellent treatment of randomized algorithms.

A nonflow-based algorithm for edge k-connectivity in tex2html_wrap_inline29042 is due to Matula [Mat87]. Faster k-connectivity algorithms are known for certain small values of k.   All three-connected components of a graph can be generated in linear time [HT73a], while tex2html_wrap_inline29044 suffices to test 4-connectivity [KR91].

Related Problems: Connected components (see page gif), network flow (see page gif), graph partition (see page gif).      

next up previous contents index CD CD Algorithms
Next: Network Flow Up: Graph Problems: Polynomial-Time Previous: Eulerian Cycle / Chinese

Mon Jun 2 23:33:50 EDT 1997