Given a universe $\mathcal{ U}=R \cup B$ of a finite set of red elements $R$, and a finite set of blue elements $B$ and a family $\mathcal{ F}$ of subsets of $\mathcal{ U}$, the \RBSC problem is to find a subset $\mathcal{ F}'$ of $\mathcal{ F}$ that covers all blue elements of $B$ and minimum number of red elements from $R$. We prove that the \RBSC problem is NP-hard even when $R$ and $B$ respectively are sets of red and blue points in ${ \rm I\!R}^2$ and the sets in $\mathcal{ F}$ are defined by axis-parallel lines i.e, every set is a maximal set of points with the same $x$ or $y$ coordinate. We then study the parameterized complexity of a generalization of this problem, where $\mathcal{ U}$ is a set of points in ${ \rm I\!R}^d$ and $\mathcal{ F}$ is a collection of set of axis-parallel hyperplanes in ${ \rm I\!R}^d$, under different parameterizations. For every parameter, we show that the problem is fixed-parameter tractable and also show the existence of a polynomial kernel. We further consider the \RBSC problem for some special types of rectangles in ${ \rm I\!R}^2$.
Categories: cs.CG