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

Author: Dinitz Y.   Nutov Z.  

Publisher: Academic Press

ISSN: 0196-6774

Source: Journal of Algorithms, Vol.32, Iss.1, 1999-07, pp. : 31-40

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The problem of finding a minimum weight k-vertex connected spanning subgraph in a graph G = (V, E) is considered. For k ≥ 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, we derive a 3-approximation algorithm for k ∈ {4, 5}. This improves the best previously known approximation ratios 416 and 41730, respectively. The complexity of the suggested algorithm is O(|V|5) for the deterministic and O(|V|4log|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.