An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding

Sharat Ibrahimpur, László A. Végh

In the Flexible Graph Connectivity (FGC) problem, we are given an undirected multigraph on $n$ vertices with nonnegative edge costs, where each edge is classified as either safe or…