Approximating Fault-Tolerant Group-Steiner Problems

Rohit Khandekar, Guy Kortsarz & Zeev Nutov
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...