A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem

✍ Scribed by Cristina G Fernandes

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 213 KB
• Volume: 28
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0931

✦ Synopsis

Consider the minimum size k-edge-connected spanning subgraph problem: given a positive integer k and a k-edge-connected graph G, find a k-edge-connected spanning subgraph of G with the minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algorithm which, for all k, achieves a performance ratio smaller than a constant which is less than two. They proved an upper bound of 1.85 for the performance ratio of their algorithm. Currently, the best known performance ratio for the problem is 1 q Ž . 2 r kq1 , achieved by a slower algorithm of Cheriyan and Thurimella. In this article, we improve Khuller and Raghavachari's analysis, proving that the performance ratio of their algorithm is smaller than 1.7 for large enough k, and that it is at most 1.75 for all k. Second, we show that the minimum size 2-edge-connected spanning subgraph problem is MAX SNP-hard.