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 (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 [Combinatorica, 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ₘₐₓ· O(ln|U|), where rₘₐₓ=maxu,v∈ Ur(u,v). This generalizes the result of Klein and Ravi [J. Algorithms, 19 (1995), pp. 104–115] for the case rₘₐₓ=1. We also give an O(ln|U|)-approximation algorithm for the node-connectivity variant of NWSN (when the paths are required to be internally disjoint) for the case rₘₐₓ=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ₘₐₓ might not exist even for $|U|=2$ and unit weights.