Set cover in which some pairs of sets are forbidden

Question

I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an approximation. I'd like to know if anyone has ever encountered a similar problem (and, if possible, have info on the approximability of the problem - I'd be glad to have a factor $f$ approximation as there is for set cover, $f$ being the maximum frequency of some element $u \in U$).

Say we're given a ground set $U$, subsets $\mathcal{S} \subseteq U$, $\overline{\mathcal{S}} \subseteq U$ and a forbidden set of pairs of the form $\{S, \overline{S} \}$ with $S \in \mathcal{S}, \overline{S} \in \overline{\mathcal{S}}$.

We can assume that every set is in exactly one forbidden pair, i.e. there is a bijection between $\mathcal{S}$ and $\overline{\mathcal{S}}$ that forms the forbidden pairs. We can also assume that $\cup_{S \in \mathcal{S}}S = \cup_{\overline{S} \in \overline{\mathcal{S}}}\overline{S} = U$, to guarantee the existence of a set cover without forbidden pairs.

Each set is also weighted by some weight function $w : \mathcal{S} \cup \overline{\mathcal{S}} \rightarrow \mathbb{R}$.

I want to find a set cover of minimum weight in which no forbidden pair is present. That is, find $S_1, \ldots, S_k \in \mathcal{S} \cup \overline{\mathcal{S}}$ of minimum total weight such that $\cup_{1 \leq i \leq k}S_i = U$ such that for any $i, j$, $\{S_i, S_j\}$ doesn't form a forbidden pair.

Answer 1

This problem is way harder than set cover. Here is why...

Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$.

We assume that $k$ is large (say, polynomial in $n$).

It is not hard to form a set system, with $n$ sets, such that any cover of the set system requires at least $\Omega(k/\log n)$ sets, and any specific set of $k$ sets cover the ground set. To this end, have a "large" ground set $X$ (say, of size $t$), and generate $n$ random sets (independently), where you pick every element $x \in X$ to be in the $i$th random set with probability roughly $p = 10(\ln n)/k$. Let $R_1, \ldots, R_n$ be the resulting random sets, and observe that a union of any specific $k$ of them covers the ground set, with high probability. Indeed, the probability that an element of $X$ is not covered, by a specific $k$ sets is bounded by $$ t (1-p)^k < 1/10, $$ for $t = n^{O(1)}$.

Similarly, consider $k' = c (k/\log n)$ random sets, where $c$ is a sufficiently small constant. We claim that with high probability their union does not cover $X$. Indeed, the probability a specific element is covered by such $k'$ sets is $1- (1-p)^{k'}$ which is a constant, say $\alpha < 1$. As such, the probability that these $k'$ random sets cover $X$ is at most $\alpha^t$. In particular, the probability that any of the possible sets of $k'$ random sets cover $X$ is bounded by $$ \alpha^t * \binom{n}{k'} < 1/10, $$ by taking $t$ to be larger than $20 (k/\alpha) \ln n$ (or some similar quantity).

Now, associate with the $v_i$ vertex in $G$, the set $R_i$. Forbid the pair $\{R_i, R_j\}$ if the edge $v_iv_j$ is in the graph $G$.

Any solution for the resulting instance, would be an independent set in $G$ of size $\Omega(k / \log n)$. The original independent set of size $k$ is a valid solution in the resulting instance (all with good probabilities). But that implies that using your problem, you can get a log approximation to independent set, which is an extremely unlikely event. More generally, a $\beta$ approximation, would imply a $O( \beta \log n)$ approximation for independent set. Since independent set can not be approximated to within $n^{1-\epsilon}$, you essentially get the same result for your problem.

PCP people might be able to derive the above from their known machinery...