On rooted node-connectivity problems

Let G be a graph which is k-outconnected from a specified root node r, that is, G has k openly disjoint paths between r and v for every node v. We giv e necessary and sufficient conditions for the existence of a pair r upsilon , rw of edges for which replacing these edges by a new edge upsilonw gives a graph that is k-outconnected from r. This generalizes a theorem of Bienst ock et al. on splitting off edges while preserving k-node-connectivity. We also prove that if C is a cycle in G such that each edge in C is critica l with respect to k-outconnectivity from r, then C has a node v, distinct f rom r, which has degree k. This result is the rooted counterpart of a theor em due to Mader. We apply the above results to design approximation algorithms for the follo wing problem: given a graph with nonnegative edge weights and node requirem ents c, for each node u, find a minimum-weight subgraph that contains max(c ,, c,) openly disjoint paths between every pair of nodes u, v. For metric w eights, our approximation guarantee is 3. For uniform weights, our approxim ation guarantee is min{2, (k + 2q - 1)/k}. Here k is the maximum node requi rement, and q is the number of positive node requirements.