Approximation algorithm for k-node connected subgraphs via critical graphs
Guy Kortsarz, Zeev Nutov · 2004
We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known ap-n proximation guarantees for this problem were O(min{k, for both directed and undirected graphs, and O(ln k) for undirected graphs with n ≥ 6k 2, where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O ( k n−k ln2 k), which is O(ln 2 k) except for very large values of k, namely, k = n − o(n). This algorithm is based on a new result on ℓ-connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio O ( √ n ln k) for all values of n, k. Combining these two gives an algorithm with approximation ratio O(ln k · min { √ k k, ln k}), which asymptotically im-n−k proves the best known approximation guarantee for directed graphs for all values of n, k, and for undirected graphs for k> n/6. Moreover, this is the first algorithm that has an n−k approximation guarantee better than Θ(k) for all values of n, k. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation to the problem. As a byproduct, we also get the following result which is of independent interest. To get a faster implementation of our algorithms, we consider the problem of adding a minimumcost edge set to increase the outconnectivity of a directed graph by ∆; a graph is said to be ℓ-outconnected from its node r if it contains ℓ internally disjoint paths from r to any other node. The best known time complexity for the later problem is O(m 3). For the particular case of ∆ = 1, we give a primal-dual algorithm with running time O(m 2). Categories and Subject Descriptors