Abstract The Survivable Network Design problem (SNDP) is a well-studied problem, (partly) motivated by the design of networks that are robust to faults under the assumption that any subset of edges up to a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. We consider three models: the flexible graph connectivity model (Adjiashvili, D.: Fault-tolerant shortest paths - beyond the uniform failure model (unpublished).) (Adjiashvili, D. et al. in Math. Program. 192 (1–2), 409–441 (2022)) (Boyd, S. et al. in Math. Program. pp. 1–24 (2023)) which was our initial motivation, the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61–77. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015)) (Adjiashvili, D. et al,: in Math. Program. 149 (1–2), 361–390 (2015)) and the relative survivable network design model (Dinitz, M. et al.: in Algorithms and Techniques (APPROX/RANDOM 2022), Leibniz International Proceedings in Informatics (LIPIcs), 245 , pp. 41:1–41:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022)) (Dinitz, M. et al.: in Algorithms, pp. 190–204. Springer Nature Switzerland, Cham (2023)). While SNDP admits a 2-approximation (Jain, K.: in Combinatorica 21 (1), 39–60 (2001)), the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when the robustness parameters are fixed constants, we consider two important special cases, namely the single pair case and the global connectivity case. For both these, we obtain constant factor approximations in several parameter ranges of interest. These are based on an augmentation framework and via decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second set of results are poly-logarithmic approximations for the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61–77. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015)) when the “width” of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. The results are obtained via two algorithmic approaches and they have different tradeoffs in terms of the approximation ratio and generality.
Rhea Jain (Mon,) studied this question.