Red Blue Set Cover Problem on Axis-Parallel Hyperplanes and Other Objects
Given a universe π°=R βͺ B of a finite set of red elements R, and a finite set of blue elements B and a family β± of subsets of π°, the problem is to find a subset β±' of β± that covers all blue elements of B and minimum number of red elements from R. We prove that the problem is NP-hard even when R and B respectively are sets of red and blue points in IR^2 and the sets in β± 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 π° is a set of points in IR^d and β± is a collection of set of axis-parallel hyperplanes in IR^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 problem for some special types of rectangles in IR^2.
READ FULL TEXT