License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2324
URN: urn:nbn:de:0030-drops-23243
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2324/
Go to the corresponding LIPIcs Volume Portal

Khandekar, Rohit ; Kortsarz, Guy ; Nutov, Zeev

Approximating Fault-Tolerant Group-Steiner Problems

pdf-format:
09005.KhandekarRohit.2324.pdf (0.2 MB)

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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2324},
  URN =		{urn:nbn:de:0030-drops-23243},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2324},
  annote =	{Keywords: Fault-tolerance, group Steiner problem, edge-disjointness, vertex-disjointness, approximation, connectivity}
}

Keywords: Fault-tolerance, group Steiner problem, edge-disjointness, vertex-disjointness, approximation, connectivity
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI