Problem level

Graph connectivity

From Algowiki
Revision as of 17:07, 6 March 2018 by ASA (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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:

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 [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

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