On Survivable Set Connectivity

In the Set Connectivity problem, we are given an n -node edge-weighted undirected graph and a collection of h set pairs ( S i, T i ), where S i and T i are subsets of nodes. The goal is to compute a min-cost subgraph H so that, for each set pair ( S i, T i ), there exists at least one path in H between some node in S i and some node in T i. In this paper, we initiate the study of the Survivable Set Connectivity problem (SSC), i. e. , the generalization of Set Connectivity where we are additionally given an integer requirement k i ≥ 1 for each set pair ( S i, T i ), and we want to find a min-cost subgraph H so that there are at least k i edge-disjoint paths in H between S i and T i. We achieve the following main results: • We show that there is no poly-logarithmic approximation for SSC unless NP has a quasi-polynomial time algorithm. This result is based on a reduction from the Minimum Label Cover problem, and the result holds even for the special case where S i = { r } for all i, i. e. , for the high-connectivity variant of the classical Group Steiner Tree problem. More precisely, we prove an approximability lower bound of 2 log1−ε n for SSC, for any constant ∊ > 0, which is almost polynomial on n. A technical novelty of our proof is the first use of a padding scheme technique for an edge-connectivity problem on undirected graphs. (Prior to our results, the applications of this technique only pertain to either node-connectivity problems or problems on directed graphs). • We present a bicriteria approximation algorithm for SSC that computes a solution H of cost at most poly-logarithmically larger than the optimal cost and provides a connectivity at least Ω ( k i /log n ) for each set pair ( S i, T i ). The main algorithmic idea is to solve a standard LP relaxation to the problem, and then embed the resulting fractional capacities into a tree via Räcke's cut-based tree embeddings. Based on that, we generate a random collection of Group Steiner Tree-like fractional solutions, which can then be handled by the rounding scheme of [Garg, Konjevod and Ravi – SODA'98]. The prior work on Set Connectivity and Group Steiner Tree used Bartal's distance-based tree embeddings which do not seem to generalize to the k -connectivity versions of these problems. Finally, we remark an interesting contrast demonstrated by our results: While our hardness result almost rules out “polynomial” approximation ratios, relaxing connectivity constraints allows us to obtain “poly-logarithmic” bounds. This naturally suggests that relaxing connectivity requirements might be a proper way in getting big improvements, even beyond (non-bicriteria) lower bounds, for other connectivity problems, especially those whose approximability lower bounds are derived from Minimum Label Cover.

Authors

• Parinya Chalermsook
• Fabrizio Grandoni 0001
• Bundit Laekhanukit

Keywords

No keywords are indexed for this paper.