2026-08-16T11:51:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2324 2024-03-06T10:33:18Z ddc:004 open_access

Approximating Fault-Tolerant Group-Steiner Problems Khandekar, Rohit Kortsarz, Guy Nutov, Zeev Fault-tolerance group Steiner problem edge-disjointness vertex-disjointness approximation connectivity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Khandekar and Guy Kortsarz and Zeev Nutov 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2324 urn:nbn:de:0030-drops-23243 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2324 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode