Approximation algorithm for k-node connected subgraphs via critical graphs

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 approximation guarantees for this problem were O (min ( k , n /√ n - k )) for both directed and undirected graphs, and O (ln k ) for undirected graphs with n ≥ 6 k 2 , where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O ( k / n - k ln 2 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 l -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 / n - k ln k )), which asymptotically improves 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 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 minimum-cost edge set to increase the outconnectivity of a directed graph by Δ a graph is said to be l -outconnected from its node r if it contains l 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 ).

Authors

• Guy Kortsarz
• Zeev Nutov

Keywords

No keywords are indexed for this paper.