Approximating Node-Connectivity Augmentation Problems

We consider the (undirected)

Node Connectivity Augmentation

(

NCA

) problem: given a graph

J

 = (

V

,

E

J

) and connectivity requirements {

r

(

u

,

v

):

u

,

v

 ∈ 

V

}, find a minimum size set

I

of new edges (any edge is allowed) so that

J

 + 

I

contains

r

(

u

,

v

) internally disjoint

uv

-paths, for all

u

,

v

 ∈ 

V

. In the

Rooted NCA

there is

s

 ∈ 

V

so that

r

(

u

,

v

) > 0 implies

u

 = 

s

or

v

 = 

s

. For large values of

k

 =  max

u

,

v

 ∈ 

V

r

(

u

,

v

),

NCA

is at least as hard to approximate as

Label-Cover

and thus it is unlikely to admit a polylogarithmic approximation.

Rooted NCA

is at least as hard to approximate as

Hitting-Set

. The previously best approximation ratios for the problem were

O

(

k

ln

n

) for

NCA

and

O

(ln

n

) for

Rooted NCA

. In [Approximating connectivity augmentation problems, SODA 2005] the author posed the following open question: Does there exist a function

ρ

(

k

) so that

NCA

admits a

ρ

(

k

)-approximation algorithm? In this paper we answer this question, by giving an approximation algorithm with ratios

O

(

k

ln

2

k

) for

NCA

and

O

(ln

2

k

) for

Rooted NCA

. This is the first approximation algorithm with ratio independent of

n

, and thus is a constant for any fixed

k

. Our algorithm is based on the following new structural result which is of independent interest. If

${\cal D}$

is a set of node pairs in a graph

J

, then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in

${\cal D}$

is

O

(ℓ

2

), where ℓ is the maximum connectivity of a pair in

${\cal D}$

.