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

A set family \(\mathcal{F}\) is uncrossable if \(A \cap B,A \cup B \in \mathcal{F}\) or \(A \setminus B,B \setminus A \in \mathcal{F}\) for any \(A,B \in \mathcal{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 \in \mathcal{F}\) we have that \(A \cap B \in \mathcal{F}\) and one of \(A \cup B,A \setminus B ,B \setminus A\) is in \(\mathcal{F}\) , or \(A \setminus B,B \setminus A \in \mathcal{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.