AIOJ

Definition

For the definitions below, see Graph-theoretic concepts:

Edge connectivity and edge cuts;
Vertex connectivity and vertex cuts;
Cliques.

Properties

Whitney's 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 of size $\lambda$ , choosing one endpoint of each edge gives a vertex cut of size $\lambda$ , so the first inequality holds.

All edges incident to a minimum-degree vertex (choose any one if there are several) form an edge cut of size $\delta$ , so the second inequality also holds.

This inequality cannot be improved; in other words, for every triple satisfying it, there is a graph realizing that triple.

Construction

Connect two cliques of size $\delta + 1$ with $\lambda$ edges, with the endpoints in each clique covering $\lambda$ and $\kappa$ distinct vertices, respectively.

Menger's theorem

It follows from the max-flow min-cut theorem, also known as the Ford–Fulkerson theorem, that the maximum number of pairwise edge-disjoint paths between two vertices equals the minimum size of a cut (this consequence is also called Menger's theorem—translators' note).

Computation

All edge weights in the graphs below are $1$ .

Computing edge connectivity with max flow

Enumerate vertex pairs $(s, t)$ and run a max flow with edge weight $s$ with $t$ as the source and $1$ as the sink. This requires $O(n^2)$ max-flow computations. With the Edmonds–Karp algorithm, the complexity is $O(|V|^3 |E|^2)$ . Dinic's algorithm is faster, with complexity $O(|V|^2 |E| \min(|V|^{2/3}, |E|^{1/2}))$ .

Global minimum cut

The Stoer–Wagner algorithm needs only one global minimum-cut computation without a specified source or sink. Its complexity is $O(|V||E| + |V|^{2}\log|V|)$ , generally approximated as $O(|V|^3)$ .

Vertex connectivity

Again enumerate vertex pairs, but this time split every non-source, non-sink vertex $x$ into $x_1$ and $x_2$ and connect them with an edge $(x_1, x_2)$ . Replace every original edge $(u, v)$ with two edges $(u_2, v_1)$ and $(v_2, u_1)$ . The max flow then equals the size of the minimum vertex cut between $s$ and $t$ (also called local vertex connectivity). The complexity is the same as when computing edge connectivity with max flow.

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

Vertex and Edge Connectivity