Approximating steiner networks with node weights

The (undirected) Steiner Network problem is: given a graph G∈=∈(V,E) with edge/node weights and edge-connectivity requirements {r(u,v):u,v∈ ∈U 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 [12], 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 ( ) problem, nontrivial approximation algorithms were known only for 0,1 requirements. We make an attempt to change this situation, by giving the first non-trivial approximation algorithm for with arbitrary requirements. Our approximation ratio for is r _max •O(ln |U|), where r _max ∈=∈ max _{u,v∈ ∈U} r(u,v). This generalizes the result of Klein and Ravi [14] for the case r _max =∈1. We also give an O(ln |U|)-approximation algorithm for the node-connectivity variant of (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. We also give the first evidence that a polylogarithmic approximation ratio for might not exist even for |U|∈=∈2 and unit weights.