when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-23243
URL:

; ;

### Approximating Fault-Tolerant Group-Steiner Problems

 pdf-format:

### Abstract

In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf 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 {\em uncros\-sable} 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.

### BibTeX - Entry

@InProceedings{khandekar_et_al:LIPIcs:2009:2324,
author =	{Rohit Khandekar and Guy Kortsarz and Zeev Nutov},
title =	{{Approximating Fault-Tolerant Group-Steiner Problems}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages =	{263--274},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-13-2},
ISSN =	{1868-8969},
year =	{2009},
volume =	{4},
editor =	{Ravi Kannan and K. Narayan Kumar},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},