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

## References

1. R. E. Gomory, T. C. Hu, Multi-terminal network flows, J. Soc. Indust. Appl. Math. 9 (1961), 551-570.Doi link.
2. R. Hariharan, T. Kavitha, D. Panigrahi, A. Bhalgat, An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs, Proceedings of 39th STOC (2007), 605-614. Doi link.