# Graph connectivity

## 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. 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. 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.