Node-weighted Network Design in Planar and Minor-closed Families of Graphs

We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = (V, E) and integer connectivity requirements r(uv) for each unordered pair of nodes uv. The goal is to find a minimum weighted subgraph H of G such that H contains r(uv) disjoint paths between u and v for each node pair uv. Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O(k)-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uvr(uv) is the maximum connectivity requirement. This improves upon the O(klog n)-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O(1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.