Approximating steiner networks with node-weights

The (undirected) Steiner Network problem is as follows: given a graph G = (V, E) with edge/node-weights and edge-connectivity requirements {r(u,v): u,v ∈ U C V}, find a minimum-weight subgraph H of G containing U so that the uv-edge-connectivity in H is at least r(u, v) for all u,v ∈ U. The seminal paper of Jain [Combinatorial, 21 (2001), pp. 39-60], and numerous papers preceding it, considered the Edge-Weighted Steiner Network problem, with weights on the edges only, and developed novel tools for approximating minimum-weight edge-covers of several types of set functions and families. However, for the Node-Weighted Steiner Network (NWSN) problem, nontrivial approximation algorithms were known only for 0, 1 requirements. We make an attempt to change this situation by giving the first nontrivial approximation algorithm for NWSN with arbitrary requirements. Our approximation ratio for NWSN is r_max · O(In |U|), where r_max = max_u,v ∈U r(u, v). This generalizes the result of Klein and Ravi [J. Algorithms, 19 (1995), pp. 104-115] for the case r_max = 1. We also give an O(In |U|)-approximation algorithm for the node-connectivity variant of NWSN (when the paths are required to be internally disjoint) for the case r_max = 2. Our results are based on a much more general approximation algorithm for the problem of finding a minimum node-weighted edge-cover of an uncrossable set-family. Finally, we give evidence that a polylogarithmic approximation ratio for NWSN with large r_max might not exist even for |U| = 2 and unit weights.