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

  1. $\lambda(G) = \min_{x,y\in V(G), x\neq y} \lambda(x,y)$ to be the (min) edge connectivity.
  2. $\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. )

  1. 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.
  • 1
    $\begingroup$ Chao, you are of aware of one case where the Gomory-Hu tree can be computed in close to $O(mn)$ time, namely unweighted undirected graphs. So, in principle, there is no need to compute $n$ max flows. $\endgroup$ Aug 20, 2014 at 4:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.