A fast algorithm for computing steiner edge connectivity

ABSTRACT

Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C³ n log n+m). This algorithm is based on an efficient construction of tree packings which generalizes Edmonds' Theorem. These packings also yield a characterization of all minimal Steiner cuts of size C from which an efficient data structure for maintaining edge connectivity between vertices in S under edge insertion can be obtained. This data structure enables the efficient construction of a cactus tree for representing significant C-cuts among these vertices, called C-separations, in the same time bound. In turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the Survivable Network Design problem due to Williamson, Goemans, Mihail and Vazirani.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When trees collide: an approximation algorithm for the generalized Steiner problem on networks, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.134-144, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103437]
• 2: 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]
• 3: Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, A faster implementation of the Goemans-Williamson clustering algorithm, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.17-25, January 07-09, 2001, Washington, D.C., United States
• 4: E.A. Dinits, A.V. Karzanov, M.V. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization, A.A. Fridman, Ed., pp. 240--306, 1976. (Original article in Russian, translation available from National Translation Center, Library of Congress, Cataloging Distribution Center, Washington D.C, 20541 (NTC 89-20265)).
• 5: Yefim Dinitz , Alek Vainshtein, The connectivity carcass of a vertex subset in a graph and its incremental maintenance, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.716-725, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195442]
• 6: Y. Dinitz and J. Westbrook. Maintaining the classes of 4-edge-connectivity in a graph on line. Algorithmica, 20, pp. 242--276, 1998.
• 7: J. Edmonds. Submodular functions, matroids, and certain polyhedra. Proceedings of the Calgary International Conference on Combinatorial Structures and their Application, Gordon and Breach, New York, 1969, pp. 69--87.
• 8: J. Edmonds. Edge Disjoint Branchings. Combinatorial Algorithms, R. Rustin, editor, Algorithmics Press, NY, 1972, pp. 91--96.
• 9: Lisa Fleischer, Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time, Journal of Algorithms, v.33 n.1, p.51-72, Oct. 1999 [doi>10.1006/jagm.1999.1039]
• 10: A. Frank. Kernel systems of directed graphs. Acta Sci. Math., 41, 1979, pp. 63--76.
• 11: Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
• 12: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
• 13: H. Gabow, M. Goemans, D. Williamson. An efficient approximation algorithm for the survivable network design problem, Proceedings of IPCO, pp. 57--74, 1993. To appear in Math. Programming.
• 14: Harold N. Gabow , Seth Pettie, The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.190-199, July 03-05, 2002
• 15: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 16: M. Grotschel, C.L. Monma, M. Stoer. Design of Survivable Networks, Handbook of Operations Research and Management Science, 1993.
• 17: K. Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, Vol 21-1, 39--60, 2001.
• 18: Philip N. Klein, A data structure for bicategories, with application to speeding up an approximation algorithm, Information Processing Letters, v.52 n.6, p.303-307, Dec. 23, 1994 [doi>10.1016/0020-0190(94)00156-1]
• 19: L. Lovasz. On two minimax theorems in graph theory. Journal of Combinatorial Theory, B, 21, 1976, pp. 96--103.
• 20: H. Nagamochi, T. Ibaraki. Linear time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7, 1992, pp. 583--596.
• 21: R. Tarjan. A good algorithm for edge-disjoint branchings. Information Processing Letters, 3, 1975, pp. 51--53.
• 22: P. Tong, E. Lawler. A faster algorithm for finding edge disjoint branchings. Information Processing Letters, 17, 2, 1983, pp. 73--76.
• 23: D. Williamson, M. Goemans, M. Mihail, V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15, pp. 435--454, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Steiner points, cactus trees, edge-connectivity