Extensions of the $(p,q)$-Flexible-Graph-Connectivity model

Abstract

We present approximation algorithms for network design problems in some models related to the $(p,q)$-FGC model. Adjiashvili, Hommelsheim and Mühlenthaler introduced the model of Flexible Graph Connectivity that we denote by FGC. Boyd, Cheriyan, Haddadan and Ibrahimpur introduced a generalization of FGC. Let $p\ge 1$ and $q\ge 0$ be integers. In an instance of the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, we have an undirected connected graph $G=(V,E)$, a partition of $E$ into a set of safe edges and a set of unsafe edges, and nonnegative costs $c\in {\mathbb{R}}_{\ge 0}^E$ on the edges. A subset $F\subseteq E$ of edges is feasible for the $(p,q)$-FGC problem if for any set of unsafe edges, $F^{\prime }$, with $|F^{\prime }|\le q$, the subgraph $(V,F\setminus F^{\prime })$ is $p$-edge connected. The algorithmic goal is to find a feasible edge-set $F$ that minimizes $c(F)={\sum }_{e\in F}{c}_e$.