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 at least $k$ nodes from a given set $T$ of terminals.