Improved approximation algorithms for min-cost connectivity augmentation problems

A graph G is k-connected if it has k internally-disjoint stpaths for every pair s, t of nodes. Given a root s and a set T of terminals is k-(s, T)-connected if it has k internally-disjoint st-paths for every t ε T. We consider two well studied mincost connectivity augmentation problems, where we are given an integer k ≥ 0, a graph G = (V,E), and and an edge set F on V with costs. The goal is to compute a minimum cost edge set J ⊆ F such that G + J has connectivity k + 1. In the k-Connectivity Augmentation problem G is k-connected and G+J should be (k+1)-connected. In the k-(s, T)-Connectivity Augmentation problem G is k-(s, T)-connected and G + J should be (k + 1)-(s, T)-connected. For the k-Connectivity Augmentation problem we obtain the following results. For n ≥ 3k - 5, we obtain approximation ratios 3 for directed graphs and 4 for undirected graphs,improving the previous ratio 5 of [26]. 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-(s, T)-Connectivity Augmentation problem we achieve ratio 4 2/3, improving the previous best ratio 12 of [24]. For the special case when all the edges in F are incident to s, we give a polynomial time algorithm, improving the ratio 4 17/30 of [21,25] for this variant.