10.4230/LIPICS.FSTTCS.2009.2324
Khandekar, Rohit
Rohit
Khandekar
Kortsarz, Guy
Guy
Kortsarz
Nutov, Zeev
Zeev
Nutov
Approximating Fault-Tolerant Group-Steiner Problems
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Fault-tolerance
group Steiner problem
edge-disjointness
vertex-disjointness
approximation
connectivity
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
2009
2009-12-14
2009-12-14
2009-12-14
en
urn:nbn:de:0030-drops-23243
10.4230/LIPIcs.FSTTCS.2009
978-3-939897-13-2
1868-8969
10.4230/LIPIcs.FSTTCS.2009
LIPIcs, Volume 4, FSTTCS 2009
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
4
23
263
274
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
4
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
222525 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 263-274