Efficient algorithms for computing all low s-t edge connectivities and related problems

ABSTRACT

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk³) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n^5/2kmin{k^1/2, n^1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n^5/6).

Our algorithm yields the useful corollary that in Õ(m + nc³) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk³) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

REFERENCES

• 1: Jorgen Bang-Jensen , Andras Frank , Bill Jackson, Preserving and Increasing Local Edge-Connectivity in Mixed Graphs, SIAM Journal on Discrete Mathematics, v.8 n.2, p.155-178, May 1995 [doi>10.1137/S0036142993226983]
• 2: András A. Benczúr , David R. Karger, Augmenting undirected edge connectivity in Õ(n2) time, Journal of Algorithms, v.37 n.1, p.2-36, Oct. 2000 [doi>10.1006/jagm.2000.1093]
• 3: Richard Cole , Ramesh Hariharan, A fast algorithm for computing steiner edge connectivity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780568]
• 4: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Journal of Computer and System Sciences, v.50 n.2, p.259-273, April 1995
• 5: Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
• 6: R. E. Gomory and T. C. Hu, Multi-terminal network flows, J. Soc. Indust. Appl. Math. 9(4) (1961), pp. 551--570.
• 7: M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.
• 8: Dan Gusfield, Very simple methods for all pairs network flow analysis, SIAM Journal on Computing, v.19 n.1, p.143-155, Feb. 1990 [doi>10.1137/0219009]
• 9: David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195422]
• 10: Hiroshi Nagamochi and Toshihide Ibaraki, A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph, Algorithmica 7(5&6) (1992), pp. 583--596.
• 11: Hiroshi Nagamochi and Toshimasa Watanabe, Computing k-Edge-Connected Components of a Multigraph, Inst. Electron. Inform. Comm, Vol E76-A, 4 (1993), pp. 513--517.
• 12: Romeo Rizzi, A simple minimum T-cut algorithm, Discrete Applied Mathematics, v.129 n.2-3, p.539-544, 01 August 2003 [doi>10.1016/S0166-218X(03)00182-3]