Extending the Primal-Dual 2-Approximation Algorithm Beyond Uncrossable Set Families

A set family F is uncrossable if A∩B,A∪B∈F or A\B,B\A∈F for any A,B∈F. 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. They asked whether this result extends to a larger class of set families and combinatorial optimization problems. We define a new class of semi-uncrossable set families, when for any A,B∈F we have that A∩B∈F and one of A∪B,A\B,B\A is in F, or A\B,B\A∈F. We will show that the Williamson et al. algorithm extends to this new class of families and identify several “non-uncrossable” algorithmic problems that belong to this class. In particular, we will show that the union of an uncrossable family and a monotone family, or of an uncrossable family that has the disjointness property and a proper family, is a semi-uncrossable family, that in general is not uncrossable. For example, our result implies approximation ratio 2 for the problem of finding a min-cost subgraph H such that H contains a Steiner forest and every connected component of H contains zero or at least k nodes from a given set T of terminals.