Vertex/Edge Connectivity

Definition

For the definitions of the following terms, please refer to Graph Theory Concepts:

Edge connectivity, edge cut set;
Vertex connectivity, vertex cut set;
Clique.

Properties

Whitney Inequality

Whitney's inequality (1932) gives the relationship between vertex connectivity \(\kappa\), edge connectivity \(\lambda\), and minimum degree \(\delta\):

\[ \kappa \le \lambda \le \delta \]

Proof

Intuitively, if there is an edge cut set of size \(\lambda\), by arbitrarily selecting one endpoint from each edge, we can obtain a vertex cut set of size \(\lambda\), so the first inequality holds.

All edges adjacent to the vertex with the minimum degree (if there are multiple, choose one arbitrarily) form an edge cut set of size \(\delta\), so the second inequality also holds.

This inequality cannot be improved; in other words, for every triple satisfying it, a graph satisfying that triple can be constructed.

Construction

Connect two cliques of size \(\delta + 1\) using \(\lambda\) edges, such that \(\lambda\) and \(\kappa\) distinct vertices in the two cliques are incident to these connecting edges, respectively.

Menger's Theorem

From the Max-Flow Min-Cut Theorem (also known as the Ford–Fulkerson theorem), it can be deduced that the maximum number of edge-disjoint paths between two vertices equals the minimum size of an edge cut separating them (this corollary is also known as Menger's theorem—translator's note).

Computation

In the following graphs, all edge weights are \(1\).

Computing Edge Connectivity via Max Flow

Enumerate vertex pairs \((s, t)\), treat \(s\) as the source and \(t\) as the sink, and run a max flow algorithm with edge weights \(1\). This requires \(O(n^2)\) max flow computations. If using the Edmonds–Karp algorithm, the complexity is \(O(|V|^3 |E|^2)\). Using Dinic's algorithm yields better complexity: \(O(|V|^2 |E| \min(|V|^{2/3}, |E|^{1/2}))\).

Global Minimum Cut

Using the Stoer–Wagner algorithm, only one source-sink-free minimum cut computation is needed. The complexity is \(O(|V||E| + |V|^{2}\log|V|)\), which can generally be approximated as \(O(|V|^3)\).

Vertex Connectivity

Still enumerate vertex pairs, but this time split each non-source/sink vertex \(x\) into two vertices \(x_1\) and \(x_2\), and add an edge \((x_1, x_2)\). Replace every original edge \((u, v)\) with two edges \((u_2, v_1)\) and \((v_2, u_1)\). Now the max flow equals the size of the minimum vertex cut set between \(s\) and \(t\) (also called local vertex connectivity). The complexity is the same as computing edge connectivity via max flow.

This page is translated from the blog posts Рёберная связность. Свойства и нахождение, Вершинная связность. Свойства и нахождение and their English translation Edge connectivity/Vertex connectivity. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.