TY - JOUR
T1 - Approximating subset k-connectivity problems
AU - Nutov, Zeev
PY - 2012/12
Y1 - 2012/12
N2 - A subset T∪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∈T; T is k-connected in J if for every s∈T the set T-{s} is k-connected to s in J. We consider the Subset k-Connectivity Augmentation problem: given a graph G=(V,E) with edge/node-costs, a node subset T∪V, and a subgraph J=(V,EJ) of G such that T is (k-1)-connected in J, find a minimum-cost augmenting edge-set F∪E-EJ such that T is k-connected in J∪F. The problem admits trivial ratio O(|T|2). We consider the case |T|>k and prove that for directed/undirected graphs and edge/node-costs, a ρ-approximation algorithm for Rooted Subset k-Connectivity Augmentation implies the following approximation ratios for Subset k-Connectivity Augmentation:b(ρ+k)+(|T|/|T|-k) 2O(log|T||T|-k), where b=1 for undirected graphs and b=2 for directed graphs.ρ×O(|T||T|-klogk). The best known values of ρ on undirected graphs are min{|T|,O(k)} for edge-costs and min{|T|,O(klog|T|)} for node-costs; for directed graphs ρ=|T| for both versions. Our results imply that unless k=|T|-o(|T|), Subset k-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].
AB - A subset T∪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∈T; T is k-connected in J if for every s∈T the set T-{s} is k-connected to s in J. We consider the Subset k-Connectivity Augmentation problem: given a graph G=(V,E) with edge/node-costs, a node subset T∪V, and a subgraph J=(V,EJ) of G such that T is (k-1)-connected in J, find a minimum-cost augmenting edge-set F∪E-EJ such that T is k-connected in J∪F. The problem admits trivial ratio O(|T|2). We consider the case |T|>k and prove that for directed/undirected graphs and edge/node-costs, a ρ-approximation algorithm for Rooted Subset k-Connectivity Augmentation implies the following approximation ratios for Subset k-Connectivity Augmentation:b(ρ+k)+(|T|/|T|-k) 2O(log|T||T|-k), where b=1 for undirected graphs and b=2 for directed graphs.ρ×O(|T||T|-klogk). The best known values of ρ on undirected graphs are min{|T|,O(k)} for edge-costs and min{|T|,O(klog|T|)} for node-costs; for directed graphs ρ=|T| for both versions. Our results imply that unless k=|T|-o(|T|), Subset k-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].
KW - Approximation algorithms
KW - Graph connectivity
UR - http://www.scopus.com/inward/record.url?scp=84871405188&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2012.08.001
DO - 10.1016/j.jda.2012.08.001
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:84871405188
SN - 1570-8667
VL - 17
SP - 51
EP - 59
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
ER -