Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families

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. 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. The approximation ratio 16 was improved to 10 in [11]. Recently, Bansal [3] obtained approximation ratio 8 for γ-pliable families and also considered an important particular case of the family of cuts of size < k of a graph H. We will improve the approximation ratio to 7 for the former case and give a simple proof of approximation ratio 6 for the latter case. Furthermore, if H is λ-edge-connected then we will show a slightly better approximation ratio 6 − 1/β+1, where β = ⌈k-1(λ+1)/2⌉ k. Our analysis is supplemented by examples indicating that these approximation ratios are asymptotically tight for the primal-dual algorithm.