A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

✍ Scribed by Yefim Dinitz; Zeev Nutov

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 103 KB
• Volume: 32
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1007

✦ Synopsis

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, Ä 4 we derive a 3-approximation algorithm for k g 4, 5 . This improves the best 1 1 7

previously known approximation ratios 4 and 4 , respectively. The complexity of 6 3 0

for the deterministic and O V log V for the randomized version. The way of solution is as follows. Analyzing a subgraph constructed by the algorithm of the aforementioned paper, we prove that all its ''small'' cuts have exactly two sides and separate a certain fixed pair of vertices.

Ž . Such a subgraph is augmented to a k-connected one optimally by at most four executions of a min-cost k-flow algorithm.