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:

• Is the graph already disconnected? - The simplest connectivity problem is testing whether the graph is in fact connected. A simple depth-first or breadth-first search suffices to identify all components in linear time, as discussed in Section .   For directed graphs, the issue is whether the graph is strongly connected, meaning there is a directed path between any pair of vertices.     In a weakly connected graph, there may exist paths to nodes from which there is no way to return.
• What if I want to split the graph into equal-sized pieces? - Often, what is sought is not the smallest set of edges or vertices whose deletion will disconnect the graph, but a small set that breaks the graph into roughly equal-sized pieces. For example, suppose we want to break a computer program spread across several files into two maintainable units. Construct a graph where the vertices are subroutines, with an edge between any two subroutines that interact, say by one calling the other. We seek to partition the routines into equal-sized sets so that the fewest pairs of interacting routines are spread across the set.    

  This is the graph partition problem, which is further discussed in Section .   Although the problem is NP-complete, reasonable heuristics exist to solve it.

• Is there one weak link in my graph? - We say that G is biconnected if no single vertex deletion is sufficient to disconnect G.     Any vertex that is such a weak point is called an articulation vertex.   A bridge is the analogous concept for edges, meaning a single edge whose deletion disconnects the graph.

  The simplest algorithms for identifying articulation vertices (or bridges) would try deleting vertices (or edges) one by one, and then using DFS or BFS to test whether the resulting graph is still connected. More complicated but linear-time algorithms exist for both problems, based on depth-first search. Implementations are described below and in Section .

• Are arbitrary cuts OK, or must I separate a given pair of vertices? - There are two flavors of the general connectivity problem. One asks for the smallest cutset for the graph, the other for the smallest set to separate from t.    Any algorithm for (-t)-connectivity can be used with each of the n(n-1)/2 possible pairs of vertices to give an algorithm for general connectivity. Less obviously, n-1 runs will suffice, since we know that vertex must end up in a different component from at least one of the other n-1 vertices in any cut set.

Both edge and vertex connectivity can be found using network flow techniques.   Network flow, discussed in Section , 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 in G is exactly the weight of the smallest set of edges to disconnect G with and in different components. Thus the edge connectivity can be found by minimizing the flow between and each of the n-1 other vertices in an unweighted graph G. Why? After deleting the minimum-edge cut set, 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 of G with two vertices and , such that edge for all , and by replacing every edge by edges , 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 .   

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 for details.

The Stanford GraphBase (see Section ) 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 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 suffices to test 4-connectivity [KR91].

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