Khandekar, Rohit ;
Kortsarz, Guy ;
Nutov, Zeev
Approximating FaultTolerant GroupSteiner Problems
Abstract
In this paper, we initiate the study of designing approximation algorithms for
{\sf FaultTolerant GroupSteiner} ({\sf FTGS}) problems. The motivation is to protect
the wellstudied groupSteiner networks from edge or vertex failures.
In {\sf FaultTolerant GroupSteiner} 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
minimumcost 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.,
edgecosts vs. vertexcosts, edgeconnectivity vs. vertexconnectivity,
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 edgeconnectivity variant, we use a primaldual based
algorithm for covering an {\em uncros\sable} setfamily, while for the vertexconnectivity version,
we prove a new graphtheoretic lemma that shows equivalence between obtaining two vertexdisjoint paths
from two vertices and $2$connecting a carefully chosen single vertex. To handle large groupsizes,
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 nontrivial 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 FaultTolerant GroupSteiner Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {263274},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897132},
ISSN = {18688969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2324},
URN = {urn:nbn:de:0030drops23243},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2324},
annote = {Keywords: Faulttolerance, group Steiner problem, edgedisjointness, vertexdisjointness, approximation, connectivity}
}
2009
Keywords: 

Faulttolerance, group Steiner problem, edgedisjointness, vertexdisjointness, approximation, connectivity 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Related Scholarly Article: 


Issue date: 

2009 
Date of publication: 

2009 