Approximating subset k-connectivity problems

A subset T⊆VT⊆V of terminals is k-connected to a root s in a directed/undirected graph J if J has k internally-disjoint vs  -paths for every v∈Tv∈T; T is k-connected in J   if for every s∈Ts∈T the set T∖{s}T∖{s} is k-connected to s in J. We consider the Subsetk-ConnectivityAugmentation problem: given a graph G=(V,E)G=(V,E) with edge/node-costs, a node subset T⊆VT⊆V, and a subgraph J=(V,EJ)J=(V,EJ) of G such that T   is (k−1)(k−1)-connected in J  , find a minimum-cost augmenting edge-set F⊆E∖EJF⊆E∖EJ such that T is k  -connected in J∪FJ∪F. The problem admits trivial ratio O(|T|2)O(|T|2). We consider the case |T|>k|T|>k and prove that for directed/undirected graphs and edge/node-costs, a ρ-approximation algorithm for Rooted Subsetk-Connectivity Augmentation implies the following approximation ratios for Subsetk-Connectivity Augmentation:(i)b(ρ+k)+(|T||T|−k)2O(log|T||T|−k), where b=1b=1 for undirected graphs and b=2b=2 for directed graphs.(ii)ρ⋅O(|T||T|−klogk). The best known values of ρ   on undirected graphs are min{|T|,O(k)}min{|T|,O(k)} for edge-costs and min{|T|,O(klog|T|)}min{|T|,O(klog|T|)} for node-costs; for directed graphs ρ=|T|ρ=|T| for both versions. Our results imply that unless k=|T|−o(|T|)k=|T|−o(|T|), Subsetk-Connectivity Augmentation admits the same ratios as the best known ones for the rooted version. This improves the ratios in Nutov (2009) [19] and Laekhanukit (2011) [15].