## Abstract

In the Set Connectivity problem, we are given an n-node edge-weighted undirected graph and a collection of h set pairs (Si, %), where Si and % are subsets of nodes. The goal is to compute a min-cost subgraph H so that, for each set pair (Si,Ti), there exists at least one path in H between some node in Si and some node in τ_{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 κ_{i} ≥ 1 for each set pair (S_{i}, τ_{i}), and we want to find a min-cost subgraph H so that there are at least hi edge-disjoint paths in H between Si and %. 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 Si = {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 2l^{og1-l} for SSC, for any constant e ≥ 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 ω(κ_{i}/log n) for each set pair (Si,Ti). 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 Racke's cut-based tree em-beddings. 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 em-beddings which do not seem to generalize to the κ-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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 |

Publisher | ACM |

Pages | 25-36 |

Number of pages | 12 |

Volume | 2015-January |

Edition | January |

Publication status | Published - 2015 |

MoE publication type | A4 Article in a conference publication |

Event | ACM-SIAM Symposium on Discrete Algorithms - San Diego, United States Duration: 4 Jan 2015 → 6 Jan 2015 Conference number: 26 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country | United States |

City | San Diego |

Period | 04/01/2015 → 06/01/2015 |