# Tag Info

Your problem can be stated as a minimum weight maximal independent set problem. Construction: 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 ...