Approximation algorithms for flexible graph connectivity

We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13–26, 2020, Math Program 1–33, 2021). Let k≥ 1 , p≥ 1 and q≥ 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 S and a set of unsafe edges U, and nonnegative costs c: E→ R≥ 0 on the edges. A subset F⊆ E of edges is feasible for the (p, q) -FGC problem if for any set F′⊆ U with | F′| ≤ q, the subgraph (V, F\ F′) is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c(F) = ∑ e∈Fce. We present a simple 2-approximation algorithm for the (1 , 1) -FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1 , 1) -FGC problem extends to a (k+ 1) -approximation algorithm for the (1 , k) -FGC problem. We present a 4-approximation algorithm for the (k, 1) -FGC problem, and an O(qlog | V|) -approximation algorithm for the (p, q) -FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1 , 1) -FGC problem by presenting a 16/11-approximation algorithm. The (p, q) -FGC problem is related to the well-known Capacitatedk-Connected Subgraph problem (denoted Cap- k-ECSS) that arises in the area of Capacitated Network Design. We give a min (k, 2 umax) -approximation algorithm for the Cap- k-ECSS problem, where umax denotes the maximum capacity of an edge.