An almost O(log k)-approximation for k-connected subgraphs
Zeev Nutov · 2009
We consider two cases of the Survivable Network Design (SND) problem: given a complete graph Gn = (V, En) with costs on the edges and connectivity requirements {r(u, v) : u, v ∈ V}, find a minimum cost subgraph G of Gn that contains r(u, v) internally disjoint uv-paths for all u, v ∈ V. Our main result is an O log k · log n n−k approximation algorithm for the k-Connected Subgraph problem (the case r(u, v) = k for all u, v ∈ V), for both directed and undirected graphs, where n = |V |. Our ratio is O(log k), unless k = n−o(n). Previously, the best known approximation guarantees for this problem were O(log 2 k) for directed/undirected graphs [Kortsarz and Nutov STOC 2004, Fakcharoenphol and Laekhanukit STOC 2008], and O(log k) for undirected graphs with k ≤ √ n/2 [Cheriyan, Vempala, and Vetta STOC 2002]. As in previous work, we consider the k-Connectivity Augmentation problem of increasing at minimum cost the connectivity of a given graph J from k − 1 to k; a ρ-approximation for it is used to derive an O(ρ · log k)approximation for k-Connected Subgraph. Fakcharoenphol and Laekhanukit showed that k-Connectivity Augmentation admits an O(log ν)-approximation algorithm, where ν is the number of minimal ”violated ” sets in J. However, we may have ν = Θ(n), so this gives only an O(log n)-approximation. We design a novel primal-dual algorithm that adds an edge set of cost ≤ opt to get ν ≤ 2n n−k. Combined with the algorithm of Fakcharoen-phol and Laekhanukit, this gives the ratio O log