In a connected simple graph G = (V(G),E(G)), each vertex is assigned one of c colors, where V(G) can be written as a union of a total of c subsets V_{ 1},...,V_{ c} and V_{ i} denotes the set of vertices of color i. A subset S of V(G) is called a selective subset if, for every i, every vertex v in V_{ i} has at least one nearest neighbor in $S \cup (V(G) \setminus V_{ i})$ that also lies in V_{ i}. The Minimum Selective Subset (MSS) problem asks for a selective subset of minimum size. We show that the MSS problem is log-APX-hard on general graphs, even when c=2. As a consequence, the problem does not admit a polynomial-time approximation scheme (PTAS) unless P = NP. On the positive side, we present a PTAS for unit disk graphs, which works without requiring a geometric representation and applies for arbitrary c. We further prove that MSS remains NP-complete in unit disk graphs for arbitrary c. In addition, we show that the MSS problem is log-APX-hard on circle graphs, even when c=2.
Categories: cs.CG cs.CC