### 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 weight $ W(e)$

Let $ P(v)$ be a function that returns the minimum total weight for vertex $ v$ to reach 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?