论文标题
轴平行的超平面和其他物体上的红色蓝色设定盖问题
Red Blue Set Cover Problem on Axis-Parallel Hyperplanes and Other Objects
论文作者
论文摘要
给定一个有限的红色元素$ r $的宇宙$ \ MATHCAL {U} = r \ cup b $，以及一组有限的蓝色元素$ b $和一个家庭$ \ Mathcal {f} $ $ \ MATHCAL {u} $的子集的子集{U} $，\ rbsc问题，\ rbsc问题是$ $ \ $ \ $ \ \ f \ f \ {这涵盖了$ b $的所有蓝色元素和$ r $的最低红色元素数量。 我们证明，即使$ r $和$ r $和$ b $分别是$ {\ rm i \！r}^2 $，\ rbsc问题也是np-hard，而$ \ rm i \！rm i \！r}^2 $以及$ \ mathcal {f} $中的集合定义为Axis-Parallel Lines I.E I.E. 然后，我们研究了此问题的概括的参数化复杂性，其中$ \ Mathcal {u} $是$ {\ rm i \！rm i \！r}^d $和$ \ MATHCAL {f} $的一组点，是$ {\ rm I \ rm I \！rm！rs！r}^d $，axis-partar Partar Partar Partar Partar Partar Partor Partorplanes集合的集合。对于每个参数，我们表明该问题是固定参数可进行的，并且还显示了多项式内核的存在。 我们进一步考虑了$ {\ rm i \！r}^2 $中某些特殊类型的矩形的\ rbsc问题。
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$.
