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, \left\| \cdot \right\|)$

, and connectivity requirements, find a minimum size set

S

 ⊂ 

M

 − 

V

of additional points, such that the unit disc graph induced by

V

 ∪ 

S

satisfies the requirements. In the (node-connectivity version of the)

Survivable Network Design Problem

(

SNDP

) we are given a graph

G

 = (

V

,

E

) with edge costs and connectivity requirements, and seek a min-cost subgraph

H

of

G

that satisfies the requirements. Let

$k = \mathop{ \max }\limits_{u,v \in 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 for the

SNDP

instance implies an

α

·

O

(

k

2

)-approximation algorithm for the

SN-MSP

instance. In particular, for the most interesting case of uniform requirement

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 [3].