Description
Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas:
- $G$ is an undirected graph
- $K \le |V|$
- $L > 0$ is the maximum limit
- Each vertex $v \in V$ has a weight $W(v)$
- Each edge $e \in E$ has a length $W(e)$
Let $P(v)$ be a function that returns the minimum length of a path (basically shortest path) from vertex $v$ to a vertex in $V'$.
The decision question is whether there exists a vertex set $V' \subseteq V, |V'| \le K$, such that:
$$ \sum_{v \in V} W(v) \cdot P(v) \le L $$
Example
Consider the following graph $G$, with $K = 1$ and $L = 9$:
Taking the set $\{v_3\}$ as $V'$ would be the solution to the question, because the total cost is:
$$ 3 \cdot 0 + 2 \cdot 2 + 1 \cdot 5 = 9 $$
Therefore, this is a yes-instance.
Question
How do I prove that this problem is in $\mathsf{NPC}$? I tried reducing a $\text{VC}$-instance to this, but that does not seem to work.
What I have tried as well is by converting the above undirected graph to a directed graph with the weighted paths already computed (this is polynomial computable):
$$ \begin{array}{l|l|l} & v_1 & v_2 & v_3 \\ \hline v_1 & 0 & 3 & 5 \\ \hline v_2 & 6 & 0 & 4 \\ \hline v_3 & 15 & 6 & 0 \end{array} $$
However, I'm not entirely sure what $\mathsf{NPC}$ problem to reduce from. I got the tip to use the $\text{CLIQUE}$ problem from this answer, but I do not see how to perform the reduction, so that seems unlikely. To me, this looks more like something that can be reduced from the $\text{KNAPSACK}$-problem or the $\text{SET COVER}$-problem, using the weights from the transformed directed graph, but I fail to see how exactly to this. I am starting to think that the transformed directed graph is of no use here.
What $\mathsf{NPC}$-problem can I use for the reduction?