2025/10/02 by Bubai Manna, Manna, Bubai
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Graph Theory and Algorithms #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2510.01931
openalex publication_date 2025/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 V1,...,Vc and Vi 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 Vi has at least one nearest neighbor in S ∪ (V(G) ∖ Vi) that also lies in Vi. 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.