Geometric dominating set: NP-complete?

Question

Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are the Euclidean distance between its endpoint vertices. Say that a set of vertices $D \subseteq V$ is a geometric dominating set if for every $v \in V$, the shortest path in the graph from $v$ to some vertex in $D$ is at most length $1$.

For example, a pentagonal wheel with spokes of length $1$ can be dominated with one vertex, but if the shortest edge length is greater than $1$, then $D$ must equal $V$:

---

---

The traditional dominating set problem has been known to be NP-complete since at least Garey & Johnson's 1979 book. My question is:

Q. Is finding a smallest geometric dominating set for a given geometric graph also NP-complete?

Conceivably it is not intractable, if the geometric structure can be exploited. Perhaps plane graphs $G$ would especially allow that exploitation. If anyone knows of references, I would appreciate pointers. Thanks!

Answer 1

I came up with an explicit construction that showed that your problem was NP-hard, even on the real line, but then I realized there's an even simpler argument:

Minimum dominating set is known to be NP-hard even for bipartite graphs, and those embed nicely. For example, you could send one part of the partition to $(0,0)$ and the other to $(1,0)$.

(If you insist that distinct vertices be represented by distinct points, then you may choose different points like $(\varepsilon,0)$ and $(1-\varepsilon,0)$ instead.)

Answer 2

as the all to all shortest paths can be calculated in polynomial time, it is also possible to determine all nodes, whose distance to some other node is not above some bound. That observation is not restricted to planar or geometric graphs.

Now, provided that a geometric dominating set of nodes exists, an idea for at least approximately determining a minimal covering set could be to iteratively add the vertex that maximizes the number of shortest paths it is on, to the cover, remove it from the graph and determine the next vertex to add to the cover.

Edit: An argument that just occured to me, is that the decision variant of the problem (i.e. the existence of a geometric cover) can be solved via an all shortest paths table, but it is not clear to me, whether and how the optimization variant is related to the existence variant.