## Abstract

Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the flexible graph connectivity model [1, 3, 4, 8], in which the edge set is partitioned into safe and unsafe edges. Given parameters p, q ≥ 1, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. We also discuss the bulk-robust model [6, 2] and the relative survivable network design model [19]. While SNDP admits a 2-approximation [32], 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 p and q are fixed, we consider two special cases. For the s-t case we obtain an approximation ratio that depends only on p, q whenever p + q > pq/2 which includes (p, 2) and (2, q) for all p, q ≥ 1. For the global connectivity case we obtain an O(q) approximation for (2, q), and an O(p) approximation for (p, 2) and (p, 3) for any p ≥ 1, and for (p, 4) when p is even. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second result is a poly-logarithmic approximation for a generalization of the bulk-robust model 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. We utilize a recent framework due to Chen et al. [17] that was designed for handling group connectivity.

Original language | English (US) |
---|---|

Title of host publication | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |

Editors | Kousha Etessami, Uriel Feige, Gabriele Puppis |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772785 |

DOIs | |

State | Published - Jul 2023 |

Externally published | Yes |

Event | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany Duration: Jul 10 2023 → Jul 14 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 261 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |
---|---|

Country/Territory | Germany |

City | Paderborn |

Period | 7/10/23 → 7/14/23 |

## Keywords

- approximation algorithm
- network design
- non-uniform faults

## ASJC Scopus subject areas

- Software