Approximating rooted connectivity augmentation problems

A graph is called ℓ-connected from U to r if there are ℓ internally disjoint paths from every node u ∈ U to r. The Rooted Subset Connectivity Augmentation Problem (RSCAP) is as follows: given a graph G=(V+r,E), a node subset U ⊆ V, and an integer k, find a smallest set F of new edges such that G+F is k-connected from U to r. In this paper we consider mainly a restricted version of RSCAP in which the input graph G is already (k-1)-connected from U to r. For this version we give an O(in|U|)-approximation algorithm, and show that the problem cannot achieve a better approximation guarantee than the Set Cover Problem (SCP) on |U| elements and with |V|-|U| sets. For the general version of RSCAP we give an O(In k In|U|)-approximation algorithm. For U=V we get the Rooted Connectivity Augmentation Problem} (RCAP). For directed graphs RCAP is polynomially solvable, but for undirected graphs its complexity status is not known: no polynomial algorithm is known, and it is also not known to be NP-hard. For undirected graphs with the input graph G being (k-1)-connected from V to r, we give an algorithm that computes a solution of size at most opt + min{opt,k}/2, where opt denotes the optimal solution size.