Abstract
We study some versions of the problem of finding the minimum size 2-connected subgraph. This problem is NP-hard (even on cubic planar graphs) and MAX SNP-hard. We show that the minimum 2-edge connected subgraph problem can be approximated to within 4/3 -ε for general graphs, improving upon the recent result of Vempala and Vetta [14]. Better approximations are obtained for planar graphs and for cubic graphs.We also consider the generalization, where requirements of 1 or 2 edge or vertex disjoint paths are specified between every pair of vertices, and the aim is to find a minimum subgraph satisfying these re- quirements. We show that this problem can be approximated within 3/2, general- izing earlier results for 2-connectivity. We also analyze the classical local opti- mization heuristics. For cubic graphs, our results imply a new upper bound on the integrality gap of the linear programming formulation for the 2-edge connectivity problem.
Partially supported by the IST Program of the EU under contract number IST-1999-14186 (ALCOM-FT). The author was supported by Deutsche Forschungsgemeinschaft (DFG) Graduate Scholarship. Part of the work by this author was done while he was visiting the Combinatorics & Optimization Dept., University of Waterloo, Ontario, Canada, during January-March, 2000, and was partially supported by NSERC grant no. OGP0138432 of Joseph Cheriyan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Carr and R. Ravi. A new bound for the 2-edge connected subgraph problem. In the Proc. 6th IPCO, LNCS 1412, 1998.
J. Cheriyan, A. Sebő and Z. Szigeti. An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. In the Proc. 6th IPCO, LNCS 1412, 1998.
C.G. Fernandes. A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem. Journal of Algorithms, 28, pp. 105–124, 1998.
A. Frank. Conservative weightings and ear-decompositions of graphs. Combinatorica, 13, pp. 65–81, 1993.
N. Garg, V. Santosh and A. Singla. Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. In the Proc. 4th ACM-SIAM SODA, pp. 103–111, 1993.
M.X. Goemans, A. Goldberg, S. Plotkin, D.B. Shmoys, È. Tardos and D.P. Williamson. Improved Approximation Algorithms for Network Design Problems. In the Proc. 5th ACMSIAM SODA, pp. 223–232, 1994.
R.L. Graham, M. Grötschel and L. Lovász, editors. Handbook of Combinatorics. Volume I. North-Holland, 1995.
M. Grigni, E. Koutsoupias and C.H. Papadimitriou. An approximation scheme for planar graph TSP. In the Proc. of the IEEE FOCS, 1995.
M. Grötschel, C. Monma and M. Stoer. Design of survivable networks. In Handbook in Operations Research and Management Science, Volume on Networks. North-Holland, 1995.
K. Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. In the Proc. of the IEEE FOCS, 1998.
S. Khuller and U. Vishkin. Biconnectivity Approximations and Graph Carvings. Journal of the ACM, 41(2), pp. 214–235, 1994.
H. Nagamochi and T. Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7, pp. 583–596, 1992.
R. Ravi and D.P. Williamson. An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica, 18(1), pp. 21–43, 1997.
S. Vempala and A. Vetta. Factor 4/3 Approximations for Minimum 2-Connected Subgraphs. In the Proc. 3rd International Workshop APPROX, LNCS 1913, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krysta, P., Kumar, V.S.A. (2001). Approximation Algorithms for Minimum Size 2-Connectivity Problems. In: Ferreira, A., Reichel, H. (eds) STACS 2001. STACS 2001. Lecture Notes in Computer Science, vol 2010. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44693-1_38
Download citation
DOI: https://doi.org/10.1007/3-540-44693-1_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41695-1
Online ISBN: 978-3-540-44693-4
eBook Packages: Springer Book Archive