5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – R B Feb 18 '15 at 6:50
  • $\begingroup$ 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? $\endgroup$ – Peter Taylor Feb 18 '15 at 9:40
  • $\begingroup$ @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. $\endgroup$ – R B Feb 18 '15 at 10:35
  • $\begingroup$ @RB, that's the way round I had it. $\endgroup$ – Peter Taylor Feb 18 '15 at 10:52
  • $\begingroup$ @PeterTaylor - so how would your mechanism prevent both sets to be chosen? $\endgroup$ – R B Feb 18 '15 at 11:02
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Manuel Lafond Feb 18 '15 at 13:26
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Feb 18 '15 at 18:12
  • 1
    $\begingroup$ Allright, this is the best answer so I'll accept it :) Thank you for time time sir ! $\endgroup$ – Manuel Lafond Feb 26 '15 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.