Approximating multiroot 3-outconnected subgraphs

Consider the following problem: Given an undirected graph with nonnegative edge costs and requirements k(u) for every node u, find a minimum-cost subg raph that contains max{k(u), k(v)} internally disjoint paths between every pair of nodes u, v. For k = max k(u) greater than or equal to 2, this probl em is NP-hard. The best-known algorithm for it has an approximation ratio o f 2(k - 1). For a general instance of the problem, for no value of k greate r than or equal to 2, a better approximation algorithm was known. We consid er the case of small requirements k(u) epsilon {1, 2, 3}; these may arise i n applications, as, in practical networks, the connectivity requirements ar e usually rather small. For this case, we give an algorithm with an approxi mation ratio of 10/3. This improves the best previously known approximation ratio of 4. Our algorithm also implies an improvement for arbitrary k. In the case in which we have an initial graph which is 2-connected, our algori thm achieves an approximation ratio of 2. (C) 2000 John Wiley & Sons, Inc.