Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $K$ such that the maximum $c(v) \forall v \in V$ is minimized?

This is like a dominating set, but each vertex covers a range of vertices, and we are interested in minimizing this range.

  • $\begingroup$ 1. In the first sentence, you say that $K$ is given, but in the third sentence you say you want to choose it. Which is it? I suspect the inputs are the graph and $k$, and the desired output is $K$. I encourage you to edit the question to clarify. 2. Given that you mention the connection to dominating set, I presume you already know that this problem is NP-hard. What kinds of answers are you looking for? Practical algorithms? (If so, can you give us any idea how large $k$ and $|V|$ typically are?) Approximation algorithms? Exponential-time exact algorithms? $\endgroup$
    – D.W.
    May 17 at 19:17
  • $\begingroup$ 1. You are correct, I want to find K. 2. Anything $\endgroup$ May 17 at 20:09
  • $\begingroup$ Have you searched for “minimum k-dominating set problem"? Have you read, for example, Solving the k‑dominating set problem on very large‑scale networks? $\endgroup$
    – John L.
    May 18 at 13:16
  • $\begingroup$ I'll take a look. Ty for the ref $\endgroup$ May 18 at 15:21
  • $\begingroup$ @JohnL. By the way, if I want to find the biggest k-dominating set of cardinality $\leq k$ such that no 2 vertices in K are closer than $d$, do you have a reference? $\endgroup$ May 18 at 15:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.