6
$\begingroup$

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$:


PentagonDomination


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!

$\endgroup$

2 Answers 2

7
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ This seems perfect, not sure why you made it community wiki. $\endgroup$
    – domotorp
    Feb 1, 2015 at 6:14
  • $\begingroup$ Brilliant---Thanks! Now the only hope left is for planar graph embeddings. $\endgroup$ Feb 1, 2015 at 12:38
  • $\begingroup$ @domotorp: I don't care about reputation. $\endgroup$
    – aorq
    Feb 1, 2015 at 13:36
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You are suggesting a greedy algorithm. I will try to think of an example that drives this to a poor solution.... $\endgroup$ Feb 1, 2015 at 0:07
  • $\begingroup$ Incidentally, "provided that a geometric dominating set of nodes exists"---Always one can choose $D=V$, and that is geometrically dominating. $\endgroup$ Feb 1, 2015 at 0:24
  • $\begingroup$ @Joseph I hope and guess you will find a nice example for which the suggested algorithm fails. $\endgroup$ Feb 1, 2015 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.