Iterated rounding algorithms for the smallest k-edge connected spanning subgraph

ABSTRACT

We present the best known algorithms for approximating the minimum cardinality undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is 1 + 1/2k + O(1/k²). The more precise version of our bound requires k ≥ 7, and for all such k it improves the longstanding bound of Cheriyan and Thurimella, 1 + 2/(k + 1) [2]. The improvement comes in two steps: First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + O(1/k√k)) versus 2n). This immediately implies that iterated rounding improves the bound of [2]. Our second step improves iterated rounding by finding good edges for rounding. For multigraphs our approximation ratio is 1 + 21/11k < 1 + 1.91/k. This improves the previous bound 1 + 2/k [6]. It is of interest since it is known that for some constant c > 0, an approximation ratio ≤ 1 + c/k implies P = NP. Our approximation ratio extends to the minimum cardinality Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding.

REFERENCES

• 1: Mao-cheng Cai, The number of vertices of degree k in a minimally k-edge-connected graph, Journal of Combinatorial Theory Series B, v.58 n.2, p.225-239, July 1993 [doi>10.1006/jctb.1993.1039 ]
• 2: Joseph Cheriyan , Ramakrishna Thurimella, Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching, SIAM Journal on Computing, v.30 n.2, p.528-560, 2000 [doi>10.1137/S009753979833920X]
• 3: Cristina G. Fernandes, A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem, Journal of Algorithms, v.28 n.1, p.105-124, July 1, 1998 [doi>10.1006/jagm.1998.0931 ]
• 4: Harold N. Gabow, Special edges, and approximating the smallest directed k-edge connected spanning subgraph, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Harold N. Gabow, An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph, SIAM Journal on Discrete Mathematics, v.19 n.1, p.1-18, 2005 [doi>10.1137/S0895480102414910]
• 6: Harold N. Gabow , Michel X. Goemans , Éva Tardos , David P. Williamson, Approximating the smallest k-edge connected spanning subgraph by LP-rounding, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica 21 (2001), pp. 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 , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994 [doi>10.1145/174652.174654]
• 11: G. Kortsarz and Z. Nutov, Approximating minimum cost connectivity problems, in Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez Ed., CRC Press, Boca Raton, FL, 2006.
• 12: L. Lovász and M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121, North-Holland, NY, 1986.
• 13: Algorithms for a network design problem with crossing supermodular demands, Networks, v.43 n.4, p.256-265, July 2004 [doi>10.1002/net.v43:4]