9
$\begingroup$

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.
$\endgroup$

migrated from cs.stackexchange.com Aug 15 '14 at 19:58

This question came from our site for students, researchers and practitioners of computer science.

  • 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$ – Chandra Chekuri Aug 20 '14 at 4:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.