Biconnectivity approximations and graph carvings

ABSTRACT

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard. We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity, our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP-hard as well. We also consider the case where the graph has edge weights. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a k-edge connected spanning subgraph. This improves an approximation factor of 3 for k = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any k (with an increased running time though).

REFERENCES

• 1: Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.325-334, September 1992, Orlando, Florida, United States
• 2: Joseph Cheriyan , Ramakrishna Thurimella, Algorithms for parallel k-vertex connectivity and sparse certificates, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.391-401, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103460]
• 3: ~EDMONDS, J. 1979. Matroid intersection. Ann. Disc. Math. 4, 185 204.
• 4: ~ESWARAN, K. P., AND TAR JAN, R. E. 1976. Augmentation problems. SIAM J. Comput. 5, ~653-665.
• 5: András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
• 6: ~FRANK, A, AND TARDOS, E. 1989. An application of submodular flows. LiE. Algebra Appl. ~114 / 115, 320 348.
• 7: Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
• 8: ~FREDERICKSON, G. N,, AND JAJ/~, J. 1981. Approximation algorithms for several graph augmenta- ~tion problems. SIAM J. Comput., 10, 2, 270 283.
• 9: ~FREDER1CKSON, G. N., AND JAJA, J. 1982. On the relationship between the biconnectivlty ~augmentation and traveling salesman problems. Theoret. Comput. Scz. 19, 2, 189-2(11.
• 10: 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]
• 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: Michel X. Goemans , Dimitris J. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Mathematical Programming: Series A and B, v.60 n.2, p.145-166, June 24, 1993 [doi>10.1007/BF01580607]
• 13: Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for edge connectivity problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.317-327, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103454]
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Martin Grötschel , Clyde L. Monma , Mechthild Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints, Operations Research, v.40 n.2, p.309-330, March–April 1992 [doi>10.1287/opre.40.2.309]
• 16: Xiaofeng Han , Pierre Kelsen , Vijaya Ramachandran , Robert Tarjan, Computing minimal spanning subgraphs in linear time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.146-156, September 1992, Orlando, Florida, United States
• 17: HARAR~, F. 1962. The maximum connectivity of a graph. Proc. Nat. Acad. Scl. 48, 1142-1146.
• 18: Tsan-sheng Hsu , Vijaya Ramachandran, A linear time algorithm for triconnectivity augmentation (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.548-559, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185418]
• 19: Tsan-sheng Hsu , Vijaya Ramachandran, On Finding a Smallest Augmentation to Biconnect a Graph, Proceedings of the 2nd International Symposium on Algorithms, p.326-335, December 16-18, 1991
• 20: JOHNSON, D. S 1982 The NP-completeness column: An ongoing guide. J. Alg. 3, 288 300.
• 21: Pierre Kelsen , Vijaya Ramachandran, On finding minimal 2-connected subgraphs, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.178-187, January 28-30, 1991, San Francisco, California, United States
• 22: Samir Khuller , Ramakrishna Thurimella, Approximation algorithms for graph augmentation, Journal of Algorithms, v.14 n.2, p.214-225, March 1993 [doi>10.1006/jagm.1993.1010]
• 23: ~Kou, L., MARKOWSKY, G. AND BERMAN, L. 1981. A fast algorithm for steiner trees, ~4cta Inf. 15, ~141 I45.
• 24: Yael Maon , Baruch Schieber , Uzi Vishkin, Parallel ear decomposition search (EDS) and st-numbering in graphs, Theoretical Computer Science, v.47 n.3, p.277-298, Nov., 1986
• 25: ~MILLER, G., AND RAMACHANDRAN, V. 1986. Efficient parallel ear decomposltion w~th applica- ~tions, manuscript.
• 26: ~MONMA, C. L., AND KO, C. W. 1989. Methods for designing survivable communication networks. ~in /'CA TO Adt,anc'ed Research Workshop (Denmark).
• 27: ~NAGAMOCHI, H., AND IBARAKI, T. 1992. Linear time algorithms for finding a sparse k-connected ~spanning subgraph of a k-connected graph Algorithmica, 7, 5/6, 583 596.
• 28: ~NAOR, D., GUSFIELD, D., AND MARTEL, C. 1990. A fast algorithm for optimally increasing the ~edge-connectivity. In Proceedings of tile 31st Anmtal 3~Vmposium on Fottndatiorls of Computc'r ~Science. IEEE, New York, pp. 698-707.
• 29: ~ROSENTHAL, A., AND GOLDNER, A. 1977. Smallest augmentations to biconnect a graph. SIAM.I. ~Comput. 6, 1, 55-66.
• 30: ~STEIGLIFZ, K., WEINER, P., AND KLEITMAN, D. J. 1969. The design of minimum-cost survivable ~networks. IEEE Trans. Circtdt Theoo,, CT-16, 4, 455 460.
• 31: ~TAKAHASHI, H., AND MATSUYAMA, A. 1980. An approximate solution for the Steiner tree ~problem in graphs. Math..htponica 24, 573-577.
• 32: TARJAN, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Cor~lpt~t. }, 4, ~146-159.
• 33: ~TARJAN, R. E., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM ,l. ~Comput. 14, 862 874.
• 34: ~VISHKIN, U. 1985. On efficient parallel strong orientation, bzf. Proc. Lett. 20, 235-240.
• 35: Toshimasa Watanabe , Akira Nakamura, Edge-connectivity augmentation problems, Journal of Computer and System Sciences, v.35 n.1, p.96-144, Aug. 1987 [doi>10.1016/0022-0000(87)90038-9]
• 36: ~WHITNEY, H. 1932. Non-separable and planar graphs. Tra~s. AMS 34, 339 362.
• 37: ~ZELIKOVSKY, A. 1993. An ll/6-approximation algorithm for the network Steincr problem. ~Algorithmica 9, 5, 463-470.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
biconnectivity, connectivity, sparse subgraphs