Title: Approximability of k-Connectivity Problems

Abstract:
We study the approximability of two network design problems: the
subset k-connectivity problem and the rooted subset k-connectivity
problem. It is trivial that the subset k-connectivity problem is at
least as hard as its rooted version. We show the converse that, when
the number of terminals is large enough, the subset k-connectivity
problem reduces to the rooted subset k-connectivity problem with a
loss of polylogarithmic factor. Then we show that the hardest instance
of the subset k-connectivity problem is when the number of terminals
is close to k. Moreover, we show that the rooted subset k-connectivity
problem is quasi-NP-hard to approximate within a factor of k^epsilon,
for some epsilon > 0 and k is sufficiently large.