Local edge-connectivity

Undirected graphs

Let G=(V,E) be an undirected graph. For $$u,v \in V$$ , the local edge-connectivity between u and v, denoted by $$\lambda_G(u,v)$$ , is the maximum number of edge-disjoint paths between u and v. By Menger's theorem, this equals the minimum number of edges whose removal disconnects u and v (or with other words the minimum degree of a set separating u and v).

More generally, if we have a non-negative capacity function c on the edges, then the local edge-connectivity between u and v, $$\lambda_c(u,v)$$ , is the minimum total capacity of edges whose removal disconnects u and v.

A local edge-connectivity requirement is a non-negative symmetric function $$r: V \times V \to {\mathbb Z}$$ . The graph G=(V,E) satisfies the requirement if $$\lambda_G(u,v) \geq r(u,v)$$ for any pair u,v of distinct nodes.

Local edge-connectivity can be computed using network flows.

Gomory-Hu tree

An important property of local edge-connectivity in undirected graphs is the existence of a Gomory-Hu tree. We state the result for the more general capacitated case. Let G=(V,E) be an undirected graph, and $$c: E \to {\mathbb R}_+$$ a non-negative capacity function. A tree T=(V,F) (not necessarily a subgraph of G) is a Gomory-Hu tree for c if for each edge $$uv \in F$$ , $$\lambda_c(u,v)$$ equals the total capacity of edges in G that go between the two components of (V,F-uv). It follows that for any pair of nodes s,t, $$\lambda_c(s,t)$$ equals the minimum of $$\lambda_c(u,v)$$ where u and v are adjacent nodes on the path from s to t in T.

Gomory and Hu proved that a Gomory-Hu tree always exists. Currently the fastest algorithm for computing the tree has expected running time Õ(mL) where L is the maximum local edge-connectivity.

Hypergraphs

Local edge-connectivity for hypergraphs can be defined similarly. A path between nodes s and t in a hypergraph H=(V,E) is an alternating sequence of nodes and edges $$s=v_0,e_1,v_1,e_2,\dots,e_k,v_k=t$$ where there is no repetition and nodes $$v_{i-1}$$ and $$v_i$$ belong to hyperedge $$e_i$$ (i=1,...,k). The local edge-connectivity $$\lambda_G(u,v)$$ between nodes u and v is the maximum number of hyperedge-disjoint paths between u and v. This equals the minimum number of hyperedges whose removal disconnects u and v.

Directed graphs

Let D=(V,A) be a directed graph. For $$u,v \in V$$ , the local arc-connectivity (or simply local edge-connectivity) from u to v, denoted by $$\lambda_D(u,v)$$ , is the maximum number of arc-disjoint directed paths from u to v. By Menger's theorem, this equals the minimum number of arcs that cover every directed u-v path (equivalently, the minimum in-degree of a set containing v and excluding u).

More generally, if we have a non-negative capacity function c on the edges, then the local arc-connectivity from u to v, $$\lambda_c(u,v)$$ , is the minimum total capacity of edges that cover every directed u-v path.

A local arc-connectivity requirement is a non-negative function $$r: V \times V \to {\mathbb Z}$$ (note that here the symmetry of r is not assumed). The digraph D=(V,A) satisfies the requirement if $$\lambda_D(u,v) \geq r(u,v)$$ for any pair u,v of distinct nodes.

Local arc-connectivity can be computed using network flows.