Vertex-Edge Domination in Unit Disk Graphs

Let \(G=(V,E)\) be a simple graph. A set \(D \in V\) is called a vertex-edge dominating set of G if for each edge \(e=(u,v)\in E\), either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex \(v\in V\), vertex-edge dominates every edge (u, v), as well as every edge adjacent to these edges. The vertex-edge dominating problem is to find a minimum vertex-edge dominating set of G. Herein, we study the vertex-edge dominating set problem in unit disk graphs and prove that this problem is NP-hard in that class of graphs. We also show that the problem admits a polynomial time approximation scheme (PTAS) in unit disk graphs.