Approximating (p,2) flexible graph connectivity via the primal-dual method
share
We consider the Flexible Graph Connectivity model (denoted FGC) introduced by Adjiashvili, Hommelsheim and Mühlenthaler (IPCO 2020, Mathematical Programming 2021), and its generalization, (p,q)-FGC, where p ≥ 1 and q ≥ 0 are integers, introduced by Boyd et al. (FSTTCS 2021). In the (p,q)-FGC model, we have an undirected connected graph G=(V,E), non-negative costs c on the edges, and a partition (𝒮, 𝒰) of E into a set of safe edges 𝒮 and a set of unsafe edges 𝒰. A subset F ⊆ E of edges is called feasible if for any set F'⊆𝒰 with |F'| ≤ q, the subgraph (V, F ∖ F') is p-edge connected. The goal is to find a feasible edge-set of minimum cost. For the special case of (p,q)-FGC when q = 2, we give an O(1) approximation algorithm, thus improving on the logarithmic approximation ratio of Boyd et al. (FSTTCS 2021). Our algorithm is based on the primal-dual method for covering an uncrossable family, due to Williamson et al. (Combinatorica 1995). We conclude by studying weakly uncrossable families, which are a generalization of the well-known notion of an uncrossable family.
READ FULL TEXT