In the classical survivable network design problem (SNDP), we are given an undirected graph G = (V, E) with costs on edges and a connectivity requirement k (s, t) for each pair of vertices. The goal is to find a minimum-cost subgraph H ⊆ G such that every pair (s, t) is connected by k (s, t) edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain FOCS’98, Combinatorica’01 gives a 2-approximation algorithm for EC-SNDP, and a decade later, an O (k 3 log n) -approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna FOCS’09, Theory Comput. ’12. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of EC-SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop a framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP Chalermsook, Grandoni, and Laekhanukit, SODA’15, and a true approximation algorithm is known only for the single-source variant with connectivity requirement k (S, T) ∈ 0, 1, 2 Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor. Comput. Sci. ’12. On the negative side, in terms of the number of connectivity demands q, we give an Ω (q /log q) -hardness result for large k, complementing the previous inapproximability results, e. g. , hardness in terms of k: k 1/5 − ε -hardness Cheriyan et al. , SODA’12; Laekhanukit, SODA’14; Chalermsook et al. , SODA’15; Manurangsi, IPL’19; hardness in terms of n: \ (2^ ^{1- n} \) -hardness Chalermsook et al. , SODA’15.
CHEN et al. (Sat,) studied this question.