TY - JOUR
T1 - Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems
AU - Nutov, Zeev
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media New York.
PY - 2018/4/1
Y1 - 2018/4/1
N2 - Let κG(s, t) denote the maximum number of pairwise internally disjoint st-paths in a graph G = (V, E). For a set T⊆ V of terminals, G is k-T-connected if κG(s, t) ≥ k for all s, t ∈ T; if T = V then G is k-connected. Given a root node s, G is k- (T, s)-connected if κG(t, s) ≥ k for all t ∈ T. We consider the corresponding min-cost connectivity augmentation problems, where we are given a graph G = (V, E) of connectivity k, and an additional edge set Ê on V with costs. The goal is to compute a minimum cost edge set J⊆ Ê such that G∪ J has connectivity k + 1. For the k-T-Connectivity Augmentation problem when Ê is an edge set on T we obtain ratio O(ln|T||T|−k), improving the ratio O(|T||T|−k⋅ln|T||T|−k) of Nutov (Combinatorica, 34(1), 95–114, 2014). For the k-Connectivity Augmentation problem we obtain the following approximation ratios. For n ≥ 3k − 5, we obtain ratio 3 for directed graphs and 4 for undirected graphs, improving the previous ratio 5 of Nutov (Combinatorica, 34(1), 95–114, 2014). For directed graphs and k = 1, or k = 2 and n odd, we further improve to 2.5 the previous ratios 3 and 4, respectively. For the undirected 2-(T, s)-Connectivity Augmentation problem we achieve ratio 423, improving the previous best ratio 12 of Nutov (ACM Trans. Algorithms, 9(1), 1, 2014). For the special case when all the edges in Ê are incident to s, we give a polynomial time algorithm, improving the ratio 41730 of Kortsarz and Nutov, (2015) and Nutov (Algorithmica, 63(1-2), 398–410, 2012) for this variant.
AB - Let κG(s, t) denote the maximum number of pairwise internally disjoint st-paths in a graph G = (V, E). For a set T⊆ V of terminals, G is k-T-connected if κG(s, t) ≥ k for all s, t ∈ T; if T = V then G is k-connected. Given a root node s, G is k- (T, s)-connected if κG(t, s) ≥ k for all t ∈ T. We consider the corresponding min-cost connectivity augmentation problems, where we are given a graph G = (V, E) of connectivity k, and an additional edge set Ê on V with costs. The goal is to compute a minimum cost edge set J⊆ Ê such that G∪ J has connectivity k + 1. For the k-T-Connectivity Augmentation problem when Ê is an edge set on T we obtain ratio O(ln|T||T|−k), improving the ratio O(|T||T|−k⋅ln|T||T|−k) of Nutov (Combinatorica, 34(1), 95–114, 2014). For the k-Connectivity Augmentation problem we obtain the following approximation ratios. For n ≥ 3k − 5, we obtain ratio 3 for directed graphs and 4 for undirected graphs, improving the previous ratio 5 of Nutov (Combinatorica, 34(1), 95–114, 2014). For directed graphs and k = 1, or k = 2 and n odd, we further improve to 2.5 the previous ratios 3 and 4, respectively. For the undirected 2-(T, s)-Connectivity Augmentation problem we achieve ratio 423, improving the previous best ratio 12 of Nutov (ACM Trans. Algorithms, 9(1), 1, 2014). For the special case when all the edges in Ê are incident to s, we give a polynomial time algorithm, improving the ratio 41730 of Kortsarz and Nutov, (2015) and Nutov (Algorithmica, 63(1-2), 398–410, 2012) for this variant.
KW - Approximation algorithm
KW - Crossing biset family
KW - Node-connectivity augmentation
UR - http://www.scopus.com/inward/record.url?scp=85020115657&partnerID=8YFLogxK
U2 - 10.1007/s00224-017-9786-5
DO - 10.1007/s00224-017-9786-5
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85020115657
SN - 1432-4350
VL - 62
SP - 510
EP - 532
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 3
ER -