Lune

FOCS2022Top-tier venue

Survivable Network Design Revisited: Group-Connectivity

Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang

Abstract

In the classical survivable network design problem (SNDP), we are given an undirected graph G−(V,E)G-(V,E) with costs on edges and a connectivity requirement k(5,t)k(5,t) for each pair of vertices. The goal is to find a minimum-cost subgraph H⊑GH\sqsubseteq G such that every pair (s,t)(s,t) are connected by k(s,t)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(k3log⁡n)−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 SNDP into the subset-to-subset setting, namely Group EC-SNDR We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group. EC-SNDE Previously only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15l, and a true approximation algorithm is known only for the single-source variant with connectivity requirement k(S,T)∈{0,1,2}k(S,T)\in\{0,1,2\} [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor Comput. Sci’12].

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. A 4 + ε approximation for k-connected subgraphsZeev NutovSODA 2020 · 3 citations

Related papers

  1. A 5/4-Approximation for Two-Edge ConnectivityMiguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim et al.STOC 2025 · 9 citations
  2. Breaching the 2-approximation barrier for the forest augmentation problemFabrizio Grandoni, Afrouz Jabal Ameli, Vera TraubSTOC 2022 · 6 citations
  3. Improved Approximation for Two-Edge-ConnectivityMohit Garg, Fabrizio Grandoni, Afrouz Jabal AmeliSODA 2023 · 5 citations
  4. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner treeJaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal AmeliSTOC 2020 · 19 citations
  5. A Better-Than-5/4-Approximation for Two-Edge ConnectivityFelix Hommelsheim, Alexander Lindermayr, Zhenwei LiuSODA 2026 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines