Improved Approximation Algorithms for Covering Pliable Set Families and Flexible Graph Connectivity

A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708–717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio 2, by a primal-dual algorithm with a reverse delete phase. Recently, Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1-15:19] showed that this algorithm achieves approximation ratio 16 for a larger class of so called γ-pliable set families, that have much weaker uncrossing properties. In this paper we will improve the approximation ratio to 10. Using this result and other techniques, we also improve approximation ratios for the following two problems related to the Capacitatedk-Edge Connected Spanning Subgraph (Cap-k-ECSS) problem. Near Min-Cuts Cover: Given a graph G₀=(V,E₀) and an edge set E on V with costs, find a min-cost edge set J⊆E that covers all cuts with at most k-1 edges of the graph G₀. We improve the approximation ratio from 16 to 10. We also obtain approximation ratio k-λ₀+1+ϵ, where λ₀ is the edge connectivity of G₀, which is better than ratio 10 when k-λ₀≤8.(k, q)-Flexible Graph Connectivity ((k, q)-FGC): Given a graph G=(V,E) with edge costs, a set U⊆E of ”unsafe” edges, and integers k, q, find a min-cost subgraph H of G such that every cut of H has at least k safe edges or at least k+q edges. We will show that (k, 1)-FGC admits approximation ratio 3.5+ϵ if k is odd (improving previous ratio 4), that (k, 2)-FGC admits approximation ratio 7+ϵ (improving previous ratio 20), and that (k, 3)-FGC admits approximation ratio 16 for k even (improving previous ratio 22). We also show that for unit costs, (k, q)-FGC admits approximation ratio α+2qk, where α≈1+O(1/k) is an approximation ratio for the Min-Sizek-Edge-Connected Spanning Subgraph problem. Near Min-Cuts Cover: Given a graph G₀=(V,E₀) and an edge set E on V with costs, find a min-cost edge set J⊆E that covers all cuts with at most k-1 edges of the graph G₀. We improve the approximation ratio from 16 to 10. We also obtain approximation ratio k-λ₀+1+ϵ, where λ₀ is the edge connectivity of G₀, which is better than ratio 10 when k-λ₀≤8. (k, q)-Flexible Graph Connectivity ((k, q)-FGC): Given a graph G=(V,E) with edge costs, a set U⊆E of ”unsafe” edges, and integers k, q, find a min-cost subgraph H of G such that every cut of H has at least k safe edges or at least k+q edges. We will show that (k, 1)-FGC admits approximation ratio 3.5+ϵ if k is odd (improving previous ratio 4), that (k, 2)-FGC admits approximation ratio 7+ϵ (improving previous ratio 20), and that (k, 3)-FGC admits approximation ratio 16 for k even (improving previous ratio 22). We also show that for unit costs, (k, q)-FGC admits approximation ratio α+2qk, where α≈1+O(1/k) is an approximation ratio for the Min-Sizek-Edge-Connected Spanning Subgraph problem.