2022/11/17 by Ishan Bansal, Bansal, Ishan, Joseph Cheriyan +5
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2211.09747
openalex publication_date 2022/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥ 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 and a set of unsafe edges, and nonnegative costs c∈ℝ≥0E on the edges. A subset F ⊆ E of edges is feasible for the (p,q)-FGC problem if for any set of unsafe edges, F', with |F'|≤ q, the subgraph (V, F ∖ F') is p-edge connected. The algorithmic goal is to find a feasible edge-set F that minimizes c(F) = ∑e ∈ F ce.