Problem level

Graph connectivity

From Algowiki
Jump to navigation Jump to search


1 Basic definitions

Let G = (V, E) be a given (directed or undirected) graph. The sequence P(u, v) of edges e_1 = (u, w_1), e_2 = (w_1, w_2), …, e_k = (w_{k-1}, v) is called a "path from the vertex u to v. In this case, the vertex v is reachable from u. It is assumed that the empty path P(u, u) leads from u to itself; that is, each vertex is reachable from itself. A nonempty path P(u, u) is called a cycle (or a closed walk).

Undirected graph is said to be connected if all its vertices are reachable from a certain vertex (or, equivalently, from any vertex of this graph).

Directed graph is said to be

  • weakly connected if the corresponding undirected graph is connected;
  • strongly connected if every vertex v is reachable from any other vertex v.

A connected component of an undirected graph is a maximum (with respect to inclusion) connected subgraph of this graph.

A strongly connected component of a directed graph is a maximum (with respect to inclusion) strongly connected subgraph. In other words, any two vertices of this subgraph belong to a cycle, and it contains all such cycles for its vertices.

A bridge in a graph is an edge whose removal increases the number of connected components.

A joint in a graph is a vertex whose removal increases the number of connected components.

A connected graph is said to be k-vertex-connected (or simply k-connected) if it has more than k vertices and remains connected after removal any k-1 of its vertices. The maximum such number k is called the vertex connectivity (or simply connectivity) of this graph. A 1-connected graph is said to be connected, while a 2-connected graph is said to be biconnected.

A connected graph is said to be k-edge-connected if it remains connected after removal any k-1 of its edges. The maximum such number k is called the "edge connectivity of this graph.

A biconnected component of a graph is a maximum (with respect to inclusion) biconnected subgraph of this graph.

2 Properties

A connected component can equivalently be defined via its set of vertices. These are:

  • all the vertices reachable from some vertex;
  • a set of vertices that are reachable from each other and are not reachable from other vertices.

The relation "a vertex v is reachable from a vertex u" is an equivalence relation. Thus, the search for the connected components of a graph is the same as the reconstruction of a complete equivalence relation from its part.

Alternative definitions of a bridge are as follows:

  • an edge is a bridge if it belongs to no cycle;
  • an edge e is a bridge if there exists a pair of vertices (u, v) of the same connected component such that any path P(u, v) between these vertices goes through this edge e.

A joint separates biconnected components (if two biconnected components have a common vertex, then this vertex is a joint).

Every vertex of a bridge is a joint (excepting the case where the bridge is the only edge incident to this vertex).

A strongly connected component is the union of all the cycles that pass through its vertices.

3 Algorithms

Connected components can be found by the following algorithms:

  • a systematic application of the breadth first search. The time complexity is O(m);
  • the use of a system of disjoint sets [1] The time complexity is O(m \alpha(m, n)). An effective multithreaded implementation is possible [2];
  • the parallel algorithm of Shiloach-Vishkin [3] The time complexity is O(\ln n), provided that n + 2m processors are used.

Strongly connected components can be found by the following algorithms:

Bridges can be found by the following algorithms:

Biconnected components can be found by the following algorithms:

  • Tarjan's algorithm[4] (in course of depth first search). The time complexity is O(m) (the algorithm also finds the corresponding joints);
  • the parallel Tarjan-Vishkin algorithm [11] The time complexity is O(\ln n), provided that O(m + n) processors are used (the algorithm is also able to find bridges);
  • the online Westbrook-Tarjan algorithm [10]. The time complexity is O(m \alpha(m, n)).

The problem of finding the vertex connectivity of a graph reduces to the search for maximal flows and can be solved in time O(\min\{k^3 + n, kn\} m)[12].

The edge connectivity of a graph can be found by using Gabow's algorithm[13] The time complexity is O(k m \ln (n^2/m)) for directed graphs and O(m + k^2 n \ln (n/k)) for undirected ones. The same algorithm is able to check the k-connectivity in time O(m + n \ln n).

4 References

  1. Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
  2. Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.
  3. Shiloach, Yossi, and Uzi Vishkin. “An O(\log n) Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.
  4. Jump up to: 4.0 4.1 Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
  5. Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.
  6. McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.
  7. Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.
  8. Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.
  9. Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  10. Jump up to: 10.0 10.1 Westbrook, Jeffery, and Robert Endre Tarjan. “Maintaining Bridge-Connected and Biconnected Components on-Line.” Algorithmica 7, no. 1 (June 1992): 433–64. doi:10.1007/BF01758773.
  11. Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  12. Henzinger, Monika R, Satish Rao, and Harold N Gabow. “Computing Vertex Connectivity: New Bounds From Old Techniques.” Journal of Algorithms 34, no. 2 (February 2000): 222–50. doi:10.1006/jagm.1999.1055.
  13. Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.