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