<p>This problem is way harder than set cover. Here is why...</p>

<p>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$.</p>

<p>We assume that $k$ is large (say, polynomial in $n$). </p>

<p>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 &lt; 1/10,
$$
for $t = n^{O(1)}$.</p>

<p>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 &lt; 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'} &lt; 1/10,
$$
by taking $t$ to be larger than $20 (k/\alpha) \ln n$ (or some similar quantity).</p>

<p>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$.</p>

<p>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.</p>

<p>PCP people might be able to derive the above from their known machinery...</p>

CC BY-SA 3.0
2015-02-18T13:26:57.770Z
Thank you for your answer.  Yes, I can picture the reduction clearly.  Do you think that the assumption that each set is in exactly one forbidden pair makes the problem somewhat easier ?
Manuel Lafond
CC BY-SA 3.0
2015-02-18T18:12:11.097Z
This is still a set cover instance with packing constraints, so I would still assume it is very hard. But I have no clue how to show this.
Sariel Har-Peled
CC BY-SA 3.0
2015-02-26T21:12:16.347Z
Allright, this is the best answer so I'll accept it :)  Thank you for time time sir !
Manuel Lafond
CC BY-SA 3.0
2015-02-18T00:49:51.143Z
2015-02-18T05:09:06.913Z
2015-02-18T05:09:06.913Z
Sariel Har-Peled
<p>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$).</p>

<p>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}}$.  </p>

<p>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.  </p>

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

<p>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.</p>

CC BY-SA 3.0
2015-02-18T06:50:07.970Z
If we forget about weights and optimization for a moment, do you know if deciding **whether a cover exists** (of any size) can be done in poly time? Otherwise, we don't really have hope in finding approximation algorithm..
R B
CC BY-SA 3.0
2015-02-18T09:40:48.883Z
Can't this be reduced to set cover by adding a dummy variable per forbidden pair, extending the two elements of the pair by the dummy variable, and adding a new set consisting solely of the dummy variable (and with weight 0) to allow the case where neither element of the pair is present?
Peter Taylor
CC BY-SA 3.0
2015-02-18T10:35:56.123Z
@PeterTaylor - I think it's the other way around - you are allowed to pick $S,\bar S$ or neither, but not allowed to pick both.
R B
CC BY-SA 3.0
2015-02-18T10:52:19.540Z
@RB, that's the way round I had it.
Peter Taylor
CC BY-SA 3.0
2015-02-18T11:02:25.893Z
@PeterTaylor - so how would your mechanism prevent both sets to be chosen?
R B
CC BY-SA 3.0
2015-02-18T13:23:04.633Z
@R B Yes we can decide in polynomial time whether a cover exists, since we can assume that choosing every set in $S$ forms a cover (though not necessarily minimum).
Manuel Lafond
CC BY-SA 3.0
2015-02-18T19:16:41.920Z
@RB, ah! OP isn't talking about *exact* set cover.
Peter Taylor
<approximation-algorithms><approximation-hardness><set-cover>
Set cover in which some pairs of sets are forbidden
Manuel Lafond
# Set cover in which some pairs of sets are forbidden

(Asked by: username_0 on 2015-02-17)

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.

**Tags:** approximation-algorithms, approximation-hardness, set-cover

> **Comments:**
> **username_1**: If we forget about weights and optimization for a moment, do you know if deciding **whether a cover exists** (of any size) can be done in poly time? Otherwise, we don't really have hope in finding approximation algorithm..  
> **username_2**: Can't this be reduced to set cover by adding a dummy variable per forbidden pair, extending the two elements of the pair by the dummy variable, and adding a new set consisting solely of the dummy variable (and with weight 0) to allow the case where neither element of the pair is present?  
> **username_1**: @PeterTaylor - I think it's the other way around - you are allowed to pick $S,\bar S$ or neither, but not allowed to pick both.  
> **username_2**: @RB, that's the way round I had it.  
> **username_1**: @PeterTaylor - so how would your mechanism prevent both sets to be chosen?  
> **username_0**: @username_1 Yes we can decide in polynomial time whether a cover exists, since we can assume that choosing every set in $S$ forms a cover (though not necessarily minimum).  
> **username_2**: @RB, ah! OP isn't talking about *exact* set cover.  

---

## 1 answers

### Answer by username_3 on 2015-02-18. Score: 6 | Accepted answer

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...

> **Comments:**
> **username_0**: Thank you for your answer.  Yes, I can picture the reduction clearly.  Do you think that the assumption that each set is in exactly one forbidden pair makes the problem somewhat easier ?  
> **username_3**: This is still a set cover instance with packing constraints, so I would still assume it is very hard. But I have no clue how to show this.  
> **username_0**: Allright, this is the best answer so I'll accept it :)  Thank you for time time sir !  

---

