Samir Khuller
Uzi Vishkin
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).
- ~BERM~.N, P., AND RAMAIYER, V. 1992. An approximation algorithm for the steiner tree problem. ~In Proceedings of the 3tzl Annual Symposium on Discrete Algorithms. ACM-S1AM, New York, ~pp. 325-334. Google Scholar
- ~CHERI'~AN, J., AND THURIMELLA, R. 1991. Algorithms for parallel k-vertex connectivity and ~sparse certificates. In Proceedings of the 23rd Anmtal Sympostum on Theory of Computing, (New ~Orleans, La., May 6-8). ACM, New York, pp. 391-401. Google Scholar
- ~EDMONDS, J. 1979. Matroid intersection. Ann. Disc. Math. 4, 185 204.Google Scholar
- ~ESWARAN, K. P., AND TAR JAN, R. E. 1976. Augmentation problems. SIAM J. Comput. 5, ~653-665.Google Scholar
- ~FRANK, A. 1992. Augmenting graphs to meet edge-connectivity requirements. SiAM J. Disc. ~Math. 5, 1, 25-53. Google Scholar
- ~FRANK, A, AND TARDOS, E. 1989. An application of submodular flows. LiE. Algebra Appl. ~114 / 115, 320 348.Google Scholar
- ~FREDER1CKSON, e. N. 1991. Ambivalent data structures for dynamic 2-edge connectivity and k ~smallest spanning trees. Ill Proceedzngs of tile 32rid Amzual Symposzum on Foundations o} ~Computer S,'tence IEEE, New York, pp. 632-641. Google Scholar
- ~FREDERICKSON, G. N,, AND JAJ/~, J. 1981. Approximation algorithms for several graph augmenta- ~tion problems. SIAM J. Comput., 10, 2, 270 283.Google Scholar
- ~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.Google Scholar
- ~GABOW, H. N 1991a. A matroid approach to finding edge connectivity and packing arbores- ~cences. In Proceedings of the 23rd Annual $?nposium on TheoO' of Computing (New Orleans, ~La., May 6-8). ACM, New York. pp 112-122. Google Scholar
- ~GABOW, H. N. 1991b. Applications of a poset representation to edge connectivity and graph ~rigidity. In Proceedings of the 32nd Annual Symposlzon on Foundatzons of Computer Sczence. ~IEEE, New York, pp. 812 822. Google Scholar
- ~GOEMANS, M. X. AND BERrSlMAS, D. J. 1993. Survivable networks, linear programming relax- ~ations and the parsimonious property. Math. Progr. 6(/, 2, 145-160. Google Scholar
- ~G^HL, Z., AND IT4UANO, G. 1991 Fully dynamic algorithms for edge-connectivity problems. In ~Proceedings of tile 23rci Annual $?mposium on Theory of ~~mputing (New Orleans, La., May ~6-8). ACM, New York, pp. 317-327. Google Scholar
- ~GAREY, M. R., AND JOIINSON, m. S 1978 Computers and Intractability: A guide to the theory of ~ NP-completcness. Freeman, San Francisco, Calif. Google Scholar
- ~GROETSCHEL, M., MONMA, C. L., AND STOER, m. 1992. Computational results with a cutting ~plane algorithm for designing communication networks with low-connectivity constraints. Oper. ~ Res. 40, 2, 309 330 Google Scholar
- ~HAN, JK., KE1,SEN, P., RAMACIiANDRAN, V., AND TARJAN, R. E. I992. Computing minimal ~spanning subgraphs in linear time, in Proceedings of the 3rd Annual Symposium on Dtscrete ~Algorithms. ACM-SIAM, New York, pp. 146-156. Google Scholar
- HARAR~, F. 1962. The maximum connectivity of a graph. Proc. Nat. Acad. Scl. 48, 1142-1146.Google Scholar
- ~HStl, T. S., AND RAMACII4NDRAN, V. 1991a. A linear tune algorithm for trlconnectivity augmen- ~tation. In Proceeding. s o~ the 32nd Annual Sympostum on Foundations of ('olnpztter Sctence. ~IEEE, New York, pp. 548-559. Google Scholar
- ~Hsu, T. S., AND RAMACIIANDRAN, V. 1991b. On finding a smallest augmentation to blconnect a ~graph In Proceedings at the 2nd Annual bzternattonal S),mposIum on Algorithms, Lecture Notes ~in Computer Science, vol. 557. Sprlnger-Vcrlag, New York, pp. 326-335. Google Scholar
- JOHNSON, D. S 1982 The NP-completeness column: An ongoing guide. J. Alg. 3, 288 300.Google Scholar
- KELSEN. P. AND RAMa~CIIANDRAN, V. 1991. On finding minimal two-connected subgraphs. In ~Proceedings of the 2nd Annual 5?mposlum on Discrete Algorithms. ACM-SIAM, New York, pp. ~178-187 Google Scholar
- ~KHUI I LR, S., AND THURIMELLA, R. 1993. Approximation algorithms for graph augmentation. J. ~Alg. 14, 2, 214-225. Google Scholar
- ~Kou, L., MARKOWSKY, G. AND BERMAN, L. 1981. A fast algorithm for steiner trees, ~4cta Inf. 15, ~141 I45.Google Scholar
- ~MAON, Y., SCmEBER, B, ~Nr) VISH}41N, U. 1986. Parallel Ear Decomposition Search (EDS) and ~s/-numbering in graphs. Thcoret. Cotnigut. Scl. 47, 277-298. Google Scholar
- ~MILLER, G., AND RAMACHANDRAN, V. 1986. Efficient parallel ear decomposltion w~th applica- ~tions, manuscript.Google Scholar
- ~MONMA, C. L., AND KO, C. W. 1989. Methods for designing survivable communication networks. ~in /'CA TO Adt,anc'ed Research Workshop (Denmark).Google Scholar
- ~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.Google Scholar
- ~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.Google Scholar
- ~ROSENTHAL, A., AND GOLDNER, A. 1977. Smallest augmentations to biconnect a graph. SIAM.I. ~Comput. 6, 1, 55-66.Google Scholar
- ~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.Google Scholar
- ~TAKAHASHI, H., AND MATSUYAMA, A. 1980. An approximate solution for the Steiner tree ~problem in graphs. Math.htponica 24, 573-577.Google Scholar
- TARJAN, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Cor~lpt~t. }, 4, ~146-159.Google Scholar
- ~TARJAN, R. E., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM ,l. ~Comput. 14, 862 874.Google Scholar
- ~VISHKIN, U. 1985. On efficient parallel strong orientation, bzf. Proc. Lett. 20, 235-240.Google Scholar
- ~WATANABE, T., AND NAKAMURA, A. 1987. Edge-connectivity augmentation problems. J. Comput. ~Syst. Sci. 35, 1, 96-144. Google Scholar
- ~WHITNEY, H. 1932. Non-separable and planar graphs. Tra~s. AMS 34, 339 362.Google Scholar
- ~ZELIKOVSKY, A. 1993. An ll/6-approximation algorithm for the network Steincr problem. ~Algorithmica 9, 5, 463-470.Google Scholar
Index Terms
- Biconnectivity approximations and graph carvings
Recommendations
Biconnectivity approximations and graph carvings
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingA 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)...
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for ...
Some forbidden subgraph conditions for a graph to have a k-contractible edge
Special issue: Combinatorics 2000An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Let K"n^- stand for the graph obtained from K"n by removing one edge. Let G be a k-connected graph (k>=5). It is known that if ...
Reviews
William Fennell Smyth
Two efficient algorithms that provide better approximate solutions to two well-known NP-hard problems are described: the computation of a smallest 2-connected spanning subgraph G *= V,E * of a given (at least 2-connected) graph G= V,E , where “2-connected” may mean either 2-edge-connected or 2-vertex-connected. Let n= V , m= E , and m *= E * . Then the 2-edge algorithm guarantees a spanning subgraph G e whose size (number of edges) is at most 3m *2 . Similarly, the 2-vertex algorithm guarantees a spanning subgraph G v whose size is at most 5m *3 . The best previous approximation algorithms for these problems could only guarantee sizes at most 2m * . Each of the new algorithms is asymptotically optimal in its time requirement, executing in O n+m time. The analysis of the effectiveness of these algorithms is facilitated by the introduction of a new data structure called a tree-carving (for the 2-edge problem) and a generalization of it called a carving (for the 2-vertex problem). A carving of G is a partitioning of V into non-empty subsets V 1 ,V 2 ,&ldots;,V k satisfying the following conditions: each subset is a node of a rooted tree G ; each nonleaf node V j of G includes a single special gray vertex, denoted g V j , that belongs to p V j , the parent set of V j in G ; and for every vertex vV i , every neighbor w of v in G that occurs in an ancestor set of V i belongs to one of the sets V i , p V i , or p p V i , where g p V i =w . The authors also consider the case in which the edges of G are weighted, showing that a k -edge connected spanning subgraph of size at most 2m * can always be computed in polynomial time. The paper is well written and represents a significant contribution to the design and analysis of connectivity algorithms.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments