Minimum Selective Subset on Unit Disk Graphs and Circle Graphs

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₁,. . . , V₂ and V₈ 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₈ has at least one nearest neighbor in S (V (G) V₈) that also lies in V₈. 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.