Abstract
One of the most important and wellstudied settings for network design is edgeconnectivity requirements. This encompasses uniform demands such as the Minimum kEdgeConnected Spanning Subgraph problem (kECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for faulttolerance larger than the connectivity. Taking inspiration from recent definitions and progress in graph spanners, we introduce and study new variants of these problems under a notion of relative faulttolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph postfaults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults.
We define and introduce these problems, and provide the first approximation algorithms: a (1+4/k)approximation for the unweighted relative version of kECSS, a 2approximation for the weighted relative version of kECSS, and a 27/4approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of 3. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jainâ€™s iterative rounding analysis that works even when the cutrequirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixedparameter algorithms that have not commonly been used in approximation algorithms.
BibTeX  Entry
@InProceedings{dinitz_et_al:LIPIcs.APPROX/RANDOM.2022.41,
author = {Dinitz, Michael and Koranteng, Ama and Kortsarz, Guy},
title = {{Relative Survivable Network Design}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {41:141:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17163},
URN = {urn:nbn:de:0030drops171632},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.41},
annote = {Keywords: Fault Tolerance, Network Design}
}
Keywords: 

Fault Tolerance, Network Design 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 