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:
This is the graph partition problem, which is further discussed in Section . Although the problem is NP-complete, reasonable heuristics exist to solve it.
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 .
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 ).