Approximating Fault-Tolerant Group-Steiner Problems

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.