When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2324
URN: urn:nbn:de:0030-drops-23243
URL: https://drops.dagstuhl.de/opus/volltexte/2009/2324/
 Go to the corresponding LIPIcs Volume Portal

### 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},