EUVIMEDEUVIMED entdecken
Crossref

Survivable Network Design with Group-to-Group Requirement

Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang

Journal of the ACM · 30.04.2026 · 73 (2) · 1-23

DOI: 10.1145/3794840 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 23.04.2026. Verfasst von Qingyun Chen und 3 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben. Gefördert von: NSF, Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 article 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 log 1-ɛ n -hardness [Chalermsook et al., SODA’15].

Förderung

  • NSF
  • Natural Science Foundation of China

Zitieren

APA

Chen, Q., Laekhanukit, B., Liao, C., & Zhang, Y. (2026). Survivable Network Design with Group-to-Group Requirement. Journal of the ACM, 73(2), 1-23. https://doi.org/10.1145/3794840

Vancouver

Chen Q, Laekhanukit B, Liao C, Zhang Y. Survivable Network Design with Group-to-Group Requirement. Journal of the ACM. 2026;73(2):1-23. doi:10.1145/3794840

BibTeX
@article{Chen2026,
  author = {Chen, Qingyun and Laekhanukit, Bundit and Liao, Chao and Zhang, Yuhao},
  title = {Survivable Network Design with Group-to-Group Requirement},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {2},
  pages = {1--23},
  doi = {10.1145/3794840}
}
Kostenlos starten →