A $(p+q{)}^{O(pq)}$-approximation for $(p,q)$-Flexible Graph Connectivity

Abstract

In the $(p,q)$-Flexible Graph Connectivity problem, the input consists of non-negative integers $p$ and $q$ and a graph $G=(V,E)$ whose edges are classified into safe and unsafe edges with non-negative edge costs. A subgraph H of G is $(p,q)$-Flex-Connected if every non-empty proper subset of vertices has either at least $p$ safe edges or at least $p+q$ total edges crossing it. The goal is to find a minimum cost subset $F\subseteq E$ of edges such that the subgraph $(V,F)$ is $(p,q)$-Flex-Connected. We give a $(p+q{)}^{O(pq)}$-approximation for this problem, which in particular implies a constant approximation for every fixed constants $p$ and $q$. We achieve this by designing a $(p+q{)}^{O(pq)}$-approximation for the augmentation problem of finding a minimum cost subset of edges to add to make a (p,q-1)-Flex-Connected graph into a (p,q)-Flex-Connected graph. Underlying the augmentation algorithm is a structural result showing that all deficient cuts can be represented by min rooted-cuts in a $(p+q{)}^{pq}$-sized collection of digraphs. This structural result was discovered by ChatGPT Astra.