For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a maximum flow computation.
Define that
- $\lambda(G) = \min_{x,y\in V(G), x\neq y} \lambda(x,y)$ to be the (min) edge connectivity.
- $\bar\lambda(G) = \max_{x,y\in V(G), x\neq y} \lambda(x,y)$ to be the max edge connectivity.
Because of max-flow min-cut theorem, the first problem is much easier. We just need to find a global min-cut, namely a partition $(S,V\backslash S)$, such that the number of edges from $S$ to $V\backslash S$ is minimized.
The global min-cut for both undirected and directed graphs can be solved in $O(nm)$ through Hao-Orlin's algorithm. $^1$
Max edge connectivity seems harder. I do not know of any algorithm that does less work than find all $\Omega(n^2)$ possible $\lambda(x,y)$ and take the max. This means $\Omega(n)$ max flow computation in undirected graphs by constructing the Gomory-Hu tree, and $\Omega(n^2)$ max flow in directed graphs.
Is there an algorithm that solves this problem faster? It seems that $\Omega(n)$ max flow is required. Since for each component we need to compute at least one $\lambda(x,y)$ for $x,y$ in the component. Or something equivalent. There are graphs with $\Omega(n)$ components, and one must determine which component contains the largest local edge connectivity. (although in that case, most max flow computation would incur constant cost. )
- Hao, Jianxiu X.; Orlin, James B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph". Journal of Algorithms 17 (3): 424. doi:10.1006/jagm.1994.1043.
