Approximating survivable networks with minimum number of steiner points

Given a graph H = ( U , E ) and connectivity requirements r = { r ( u , v ) : u , v ∈ R ⊆ U }, we say that H satisfies r if it contains r ( u , v ) pairwise internally‐disjoint uv ‐paths for all u , v ∈ R . We consider the Survivable Network with Minimum Number of Steiner Points (SN‐MSP) problem: given a finite set V of points in a normed space ( M , ‖·‖) and connectivity requirements, find a minimum size set S ⊂ M \ V of additional points, such that the unit disc graph induced by U = V ∪ S satisfies the requirements. In the (node‐connectivity) Survivable Network Design Problem (SNDP) we are given a graph G = ( V , E ) with edge costs and connectivity requirements, and seek a minimum cost subgraph H of G that satisfies the requirements. Let k = max u,v ∈ V r ( u , v ) denote the maximum connectivity requirement. We will show a natural transformation of an SN‐MSP instance ( V , r ) into an SNDP instance ( G = ( V , E ), c , r ), such that an α‐approximation algorithm for the SNDP instance implies an α · O ( k 2 )‐approximation algorithm for the SN‐MSP instance. In particular, for the case of uniform requirements r ( u , v ) = k for all u , v ∈ V , we obtain for SN‐MSP the ratio O ( k 2 ln k ), which solves an open problem from (Bredin et al. Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2005), 309–319). © 2012 Wiley Periodicals, Inc. NETWORKS, 2012