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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.