Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911456336805888 |
|---|---|
| author | Manna, Bubai |
| author_facet | Manna, Bubai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01931 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum Selective Subset on Unit Disk Graphs and Circle Graphs Manna, Bubai Computational Geometry Computational Complexity 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. |
| title | Minimum Selective Subset on Unit Disk Graphs and Circle Graphs |
| topic | Computational Geometry Computational Complexity |
| url | https://arxiv.org/abs/2510.01931 |