# Approximating Fault-Tolerant Group-Steiner problems

Rohit Khandekar, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In Fault-Tolerant Group-Steiner problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and 2-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an uncrossable set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and 2-connecting a carefully chosen single vertex. To handle large group-sizes, we use a p-Steiner tree algorithm to identify the "correct" pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.

اللغة الأصلية الإنجليزيّة Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings 263-274 12 https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2324 نُشِر - 2009 29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - Kanpur, الهندالمدة: ١٥ ديسمبر ٢٠٠٩ → ١٧ ديسمبر ٢٠٠٩

### سلسلة المنشورات

الاسم Leibniz International Proceedings in Informatics, LIPIcs 4 1868-8969

### !!Conference

!!Conference 29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 الهند Kanpur ١٥/١٢/٠٩ → ١٧/١٢/٠٩

### ملاحظة ببليوغرافية

Funding Information:
We would like to thank an anonymous referee for his comments that helped considerably improve the presentation of the paper. The second author was partially supported by NSF grant 08129959.

## بصمة

أدرس بدقة موضوعات البحث “Approximating Fault-Tolerant Group-Steiner problems'. فهما يشكلان معًا بصمة فريدة.