Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In 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 uncrossable 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. © Khandekar, Kortsarz, and Nutov.
Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
Mohammadtaghi Hajiaghayi, Rohit Khandekar, et al.
ACM Transactions on Algorithms
Nikhil Bansal, Zachary Friggstad, et al.
ACM Transactions on Algorithms
Eran Halperin, Guy Kortsarz, et al.
SIAM Journal on Computing