# algorithms – Minimum set cover with incompatible sets

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