A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

ABSTRACT

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, E) and an edge set E on V disjoint to E, find a minimum-size subset of edges F ⊆ E such that (V, E ∪ F) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ϵ of Nagamochi.

REFERENCES

• 1: Joseph Cheriyan , Tibor Jordán , R. Ravi, On 2-Coverings and 2-Packings of Laminar Families, Proceedings of the 7th Annual European Symposium on Algorithms, p.510-520, July 16-18, 1999
• 2: Eswaran, K. P. and Tarjan, R. E. 1976. Augmentation problems. SIAM J. Comput. 5, 653--665.
• 3: Guy Even , Jon Feldman , Guy Kortsarz , Zeev Nutov, A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.90-101, August 18-20, 2001
• 4: Frederickson, G. N. and Jájá, J. 1981. Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 270--283.
• 5: Frederickson, G. N. and Jájá, J. 1982. On the relationship between the biconnectivity augmentation and traveling salesman problem. Theor. Comput. Sci. 19, 2, 189--201.
• 6: 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]
• 7: Jain, K. 2001. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21, 1, 39--60.
• 8: Raja Jothi , Balaji Raghavachari , Subramanian Varadarajan, A 5/4-approximation algorithm for minimum 2-edge-connectivity, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Samir Khuller, Approximation algorithms for finding highly connected subgraphs, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: 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]
• 11: Kortsarz, G. and Nutov, Z. 2007. Approximating minimum cost connectivity problems. In Handbook of Approximation Algorithms and Metahueristics, T. F. Gonzales, Ed. Chapman & Hall/CRC (Chapter 58).
• 12: Maduel, Y. and Nutov, Z. 2008. Covering a laminar family by leaf to leaf links. Manuscript.
• 13: Hiroshi Nagamochi, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Discrete Applied Mathematics, v.126 n.1, p.83-113, March 2003 [doi>10.1016/S0166-218X(02)00218-4]

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:
Theory

Keywords:
Approximation algorithms, connectivity, graphs