Graph connectivity
1 Basic definitions
Let [math]G = (V, E)[/math] be a given (directed or undirected) graph. The sequence [math]P(u, v)[/math] of edges [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] is called a "path from the vertex [math]u[/math] to [math]v[/math]. In this case, the vertex [math]v[/math] is reachable from [math]u[/math]. It is assumed that the empty path [math]P(u, u)[/math] leads from [math]u[/math] to itself; that is, each vertex is reachable from itself. A nonempty path [math]P(u, u)[/math] 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 [math]v[/math] is reachable from any other vertex [math]v[/math].
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 [math]k[/math]-vertex-connected (or simply [math]k[/math]-connected) if it has more than [math]k[/math] vertices and remains connected after removal any [math]k-1[/math] of its vertices. The maximum such number [math]k[/math] 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 [math]k[/math]-edge-connected if it remains connected after removal any [math]k-1[/math] of its edges. The maximum such number [math]k[/math] 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 [math]v[/math] is reachable from a vertex [math]u[/math]" 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 [math]e[/math] is a bridge if there exists a pair of vertices [math](u, v)[/math] of the same connected component such that any path [math]P(u, v)[/math] between these vertices goes through this edge [math]e[/math].
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 [math]O(m)[/math];
- the use of a system of disjoint sets ^{[1]} The time complexity is [math]O(m \alpha(m, n))[/math]. An effective multithreaded implementation is possible ^{[2]};
- the parallel algorithm of Shiloach-Vishkin ^{[3]} The time complexity is [math]O(\ln n)[/math], provided that [math]n + 2m[/math] processors are used.
Strongly connected components can be found by the following algorithms:
- Tarjan's algorithm^{[4]} (in course of depth first search). The time complexity is [math]O(m)[/math];
- the parallel DCSC algorithm^{[5]}^{[6]}^{[7]} The complexity is [math]O(n \ln n)[/math].
Bridges can be found by the following algorithms:
- Tarjan's bridge-finding algorithm^{[8]} (in course of depth first search). The time complexity is [math]O(m)[/math];
- the parallel Tarjan-Vishkin algorithm^{[9]} The time complexity is [math]O(\ln n)[/math], provided that [math]O(m + n)[/math] processors are used;
- the online Westbrook-Tarjan algorithm ^{[10]} The time complexity is [math]O(m \alpha(m, n))[/math].
Biconnected components can be found by the following algorithms:
- Tarjan's algorithm^{[4]} (in course of depth first search). The time complexity is [math]O(m)[/math] (the algorithm also finds the corresponding joints);
- the parallel Tarjan-Vishkin algorithm ^{[11]} The time complexity is [math]O(\ln n)[/math], provided that [math]O(m + n)[/math] processors are used (the algorithm is also able to find bridges);
- the online Westbrook-Tarjan algorithm ^{[10]}. The time complexity is [math]O(m \alpha(m, n))[/math].
The problem of finding the vertex connectivity of a graph reduces to the search for maximal flows and can be solved in time [math]O(\min\{k^3 + n, kn\} m)[/math]^{[12]}.
The edge connectivity of a graph can be found by using Gabow's algorithm^{[13]} The time complexity is [math]O(k m \ln (n^2/m))[/math] for directed graphs and [math]O(m + k^2 n \ln (n/k))[/math] for undirected ones. The same algorithm is able to check the [math]k[/math]-connectivity in time [math]O(m + n \ln n)[/math].
4 References
- ↑ 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.
- ↑ 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.
- ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.
- ↑ ^{4.0} ^{4.1} Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
- ↑ ^{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.
- ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
- ↑ 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.
- ↑ 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.