标题： 某些图类上的最小选择子集 显示英文标题

标题： Minimum Selective Subset on Some Graph Classes

摘要： 在一个连通的简单图 G = (V(G),E(G)) 中，每个顶点都从颜色集合 C={1, 2,..., c}中分配一种颜色。 顶点集 V(G) 被划分为 V_1, V_2, ... ,V_c，其中所有在 V_j 中的顶点都具有相同的颜色 j。 V(G) 的一个子集 S 被称为选择子集，如果对于 V(G) 中的每个顶点 v，如果 v 在 V_j 中，则在 (S union (V(G) V_j)) 中至少有一个最近邻与 v 具有相同颜色。 最小选择子集（MSS）问题旨在找到一个最小大小的选择子集。 该问题最早由 Wilfong 于 1991 年在欧几里得平面上的一组点中提出，其中提出了两个主要问题，MCS（最小一致子集）和 MSS。 在图算法中，唯一已知的结果是 MSS 问题是 NP 完全的，如 2018 年所示。 除此之外，到目前为止没有进一步的进展。 相比之下，MCS 问题多年来在各种图类中得到了广泛研究。 因此，在这项工作中，我们还扩展了在各种图类上 MSS 的算法研究。 我们首先为具有 n 个顶点且不管颜色数量如何的一般图提供了一个 log(n)-近似算法。 我们还表明，当仅限于两种颜色时，该问题在平面图中仍然保持 NP 完全。 最后，我们提供了在树和单位区间图上计算任意数量颜色下的最优解的多项式时间算法。 显示英文摘要

摘要： In a connected simple graph G = (V(G),E(G)), each vertex is assigned a color from the set of colors C={1, 2,..., c}. The set of vertices V(G) is partitioned as V_1, V_2, ... ,V_c, where all vertices in V_j share the same color j. A subset S of V(G) is called Selective Subset if, for every vertex v in V(G), and if v is in V_j, at least one of its nearest neighbors in (S union (V(G)\ V_j)) has the same color as v. The Minimum Selective Subset (MSS) problem seeks to find a selective subset of minimum size. The problem was first introduced by Wilfong in 1991 for a set of points in the Euclidean plane, where two major problems, MCS (Minimum Consistent Subset) and MSS, were proposed. In graph algorithms, the only known result is that the MSS problem is NP-complete, as shown in 2018. Beyond this, no further progress has been made to date. In contrast, the MCS problem has been widely studied in various graph classes over the years. Therefore, in this work, we also extend the algorithmic study of MSS on various graph classes. We first present a log(n)-approximation algorithm for general graphs with n vertices and regardless of the number of colors. We also show that the problem remains NP-complete in planar graphs when restricted to just two colors.. Finally, we provide polynomial-time algorithms for computing optimal solutions in trees and unit interval graphs for any number of colors.