I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).

To state it more formally: We have a finite base set $X$ and a family $\mathcal{R}$ of subsets of $X$. We also have an undirected graph $G$ with vertex set $\mathcal{R}$ and edges representing incompatibilities between sets. The goal is to find a minimum set cover of $X$ which is also an independent set of $G$.

Does this problem have a name? Or is it a special case of a studied problem? Or can it be reduced to a well-studied problem with a small blowup in runtime? (by "small blowup" I mean not simply polynomial, but preferably a small degree polynomial).

I'm particularly interested in the geometric variant where $X$ is a set of points and the sets in $\mathcal{R}$ are defined as the intersection of $X$ with some simple geometric ranges (in which case tools such as VC-dimension, $\epsilon$-nets, range-searching and so on might come in handy for approximation algorithms). But I welcome any relevant reference.

  • $\begingroup$ I don't know a particular name, but instead of being a special case of a studied problem, it is more like the minimum set cover problem is a special case of your problem, in which the graph $G$ has no edge. Since the minimum set cover problem is known to be NP-hard, it's the same for your problem. $\endgroup$ – Nathaniel Mar 1 at 15:52
  • $\begingroup$ @Nathaniel Yes, I am aware this problem is NP-hard (quite trivially, as you point out). Still, I'm interested in finding out what more the litterature possibly has to say for this specific problem (or a closely related one) such as fastest known algorithms (which will necessarily be superpolynomial), algorithms with guaranteed approximation factors, etc. I don't mean to implement anything or apply any of this for practical purposes, I'm simply interested in the theoretical state of the art. $\endgroup$ – Tassle Mar 1 at 16:36

Your problem can be stated as a minimum weight maximal independent set problem.


Construct a bipartite graph $G = (L,R,E)$, where the right partition $R$ corresponds to $\mathcal{R}$ and the left partition $L$ corresponds to $X$. An edge $(u,v) \in E$ iff an element $u$ is contained in the set $v$.

Let $G'$ be the updated graph obtained by adding edges within $R$ based on the incompatibility of vertices in $R$.

Furthermore, assign a weight of $\infty$ on each vertex of $L$ and weight $1$ on each vertex of $R$. Also, attach a new pendant vertex of weight $0$ to each vertex in $R$. Let $G_{w}$ be this new graph.

Now, your problem can be stated as finding minimum weight maximal independent set problem (MMIS) on $G_{w}$. It is a standard problem discussed here. Your problem has a feasible solution if and only if MMIS has a finite value. Also, your problem has a solution of size $k$ if and only if MMIS has a value $k$.


Suppose, a feasible instance of the independent set cover problem is $S_{1}, \dotsc, S_{k}$. Then, the maximal independent set contains vertices in $R$ corresponding to $S_{1}, \dotsc, S_{k}$ and pendant vertices corresponding to the remaining sets. It is easy to see that it is an independent set and it is also maximal. Moreover, the weight of the independent set is exactly $k$.

Similarly, you can prove the other direction, i.e., if there is a maximal independent set of value $k$, there is an independent set cover of size $k$.

Note: Instead of assigning $\infty$ value to the vertices in $L$, you can also assign some sufficiently large finite value, say $|\mathcal{R}|+1$. That will also work.

  • $\begingroup$ It's a shame the MWMIS problem is so hard to approximate, and this reduction is thus not (directly) useful for that purpose :( But this answers the question as I asked it and gives me some direction in which I can look, so accepted anyway :) $\endgroup$ – Tassle Mar 2 at 12:18
  • $\begingroup$ @Tassle I believe that there could be some other reduction to some simpler problem. But I have not thought much about it. And, this is the only thing that I could come up with in a short span of time. May be you can unaccept the answer in hope to receive some other better answers :) It would be better that way. :p $\endgroup$ – Inuyasha Yagami Mar 2 at 13:23
  • 1
    $\begingroup$ Okay, I'll unaccept temporarily, and accept again in some time if I get no better answer :) $\endgroup$ – Tassle Mar 2 at 14:18

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.