论文标题
图表上的红蓝色分离问题
The RED-BLUE SEPARATION problem on graphs
论文作者
论文摘要
We introduce the Red-Blue Separation problem on graphs, where we are given a graph $G=(V,E)$ whose vertices are colored either red or blue, and we want to select a (small) subset $S \subseteq V$, called red-blue separating set, such that for every red-blue pair of vertices, there is a vertex $s \in S$ whose closed neighborhood contains exactly one of the two vertices of the pair.我们研究了红蓝色分离的计算复杂性，其中询问给定的红蓝色彩色图是否具有红色蓝色分离尺寸的大小最多，最多是给定整数。我们证明，即使对于受限制的图形类别，问题也是NP填充。我们还表明，在多项式时间内始终可以在$ 2 \ ln n $中近似，其中$ n $是输入图的订单。相反，对于无三角形图和有界最大程度的图形，我们表明当较小颜色类的大小由常数界定时，红蓝色的分离是可以在多项式时间内解决的。但是，在一般图上，我们表明问题是$ W [2] $ - 即使通过解决方案大小和较小颜色类的大小进行参数时，也很难。我们还考虑了最大红蓝色分离的问题，其中着色不是输入的一部分。在这里，给定输入图$ g $，我们想确定最小的整数$ k $，这样，对于每种可能的$ g $的红蓝色着色，最多有$ k $的红蓝色分离尺寸。我们在最佳红蓝色分离的最佳解决方案的基数上得出了紧密的边界，表明它的范围从图表中的对数范围为范围，到订单减去一个。我们还为相关参数提供了界限。但是，对于树木，我们证明了秩序三分之二的上限。然后，我们表明，即使对于有界的最大程度的图，也可以在多项式时间内近似于$ o（\ ln^2 n）$，也可以在多项式时间内近似。
We introduce the Red-Blue Separation problem on graphs, where we are given a graph $G=(V,E)$ whose vertices are colored either red or blue, and we want to select a (small) subset $S \subseteq V$, called red-blue separating set, such that for every red-blue pair of vertices, there is a vertex $s \in S$ whose closed neighborhood contains exactly one of the two vertices of the pair. We study the computational complexity of Red-Blue Separation, in which one asks whether a given red-blue colored graph has a red-blue separating set of size at most a given integer. We prove that the problem is NP-complete even for restricted graph classes. We also show that it is always approximable in polynomial time within a factor of $2\ln n$, where $n$ is the input graph's order. In contrast, for triangle-free graphs and for graphs of bounded maximum degree, we show that Red-Blue Separation is solvable in polynomial time when the size of the smaller color class is bounded by a constant. However, on general graphs, we show that the problem is $W[2]$-hard even when parameterized by the solution size plus the size of the smaller color class. We also consider the problem Max Red-Blue Separation where the coloring is not part of the input. Here, given an input graph $G$, we want to determine the smallest integer $k$ such that, for every possible red-blue coloring of $G$, there is a red-blue separating set of size at most $k$. We derive tight bounds on the cardinality of an optimal solution of Max Red-Blue Separation, showing that it can range from logarithmic in the graph order, up to the order minus one. We also give bounds with respect to related parameters. For trees however we prove an upper bound of two-thirds the order. We then show that Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can be approximated in polynomial time within a factor of $O(\ln^2 n)$.
