Local edge-connectivity
Undirected graphs
Let G=(V,E) be an undirected graph. For [math]u,v \in V[/math], the local edge-connectivity between u and v, denoted by [math]\lambda_G(u,v)[/math], 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, [math]\lambda_c(u,v)[/math], is the minimum total capacity of edges whose removal disconnects u and v.
A local edge-connectivity requirement is a non-negative symmetric function [math]r: V \times V \to {\mathbb Z}[/math]. The graph G=(V,E) satisfies the requirement if [math]\lambda_G(u,v) \geq r(u,v)[/math] 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 [math]c: E \to {\mathbb R}_+[/math] 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 [math]uv \in F[/math], [math]\lambda_c(u,v)[/math] 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, [math]\lambda_c(s,t)[/math] equals the minimum of [math]\lambda_c(u,v)[/math] where u and v are adjacent nodes on the path from s to t in T.
Gomory and Hu[1] proved that a Gomory-Hu tree always exists. Currently the fastest algorithm for computing the tree has expected running time Õ(mL)[2] 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 [math]s=v_0,e_1,v_1,e_2,\dots,e_k,v_k=t[/math] where there is no repetition and nodes [math]v_{i-1}[/math] and [math]v_i[/math] belong to hyperedge [math]e_i[/math] (i=1,...,k). The local edge-connectivity [math]\lambda_G(u,v)[/math] 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 [math]u,v \in V[/math], the local arc-connectivity (or simply local edge-connectivity) from u to v, denoted by [math]\lambda_D(u,v)[/math], 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, [math]\lambda_c(u,v)[/math], is the minimum total capacity of edges that cover every directed u-v path.
A local arc-connectivity requirement is a non-negative function [math]r: V \times V \to {\mathbb Z}[/math] (note that here the symmetry of r is not assumed). The digraph D=(V,A) satisfies the requirement if [math]\lambda_D(u,v) \geq r(u,v)[/math] for any pair u,v of distinct nodes.
Local arc-connectivity can be computed using network flows.
