# Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

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.

• 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?
– D.W.
May 17 at 19:17
• 1. You are correct, I want to find K. 2. Anything May 17 at 20:09
• 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? May 18 at 13:16
• I'll take a look. Ty for the ref May 18 at 15:21
• @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? May 18 at 15:40