Survivable Network Design Revisited: Group-Connectivity

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(5, t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\sqsubseteq G$ such that every pair $(s, t)$ are 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 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)\in\{0, 1, 2\}$ [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor Comput. Sci’12].

Authors

• Qingyun Chen
• Bundit Laekhanukit
• Chao Liao
• Yuhao Zhang 0001

Keywords

• Computer science
• Costs
• Approximation algorithms
• Network Design
• Undirected
• Estimation Algorithm
• Pair Of Vertices
• Network Design Problem
• Cylindrical
• Black Box
• Pathfinding
• Tree Height
• Flow Values
• Sample Trees
• Red Edge
• Approximate Ratio
• Distribution Of Trees
• Original Graph
• Constant Probability
• Fractional Solution
• Tree Edges
• Path Tree
• Green Edges