# Reduction to a vertex cover problem-like with weighted vertices and edges

### 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?

• Why doesn't it work? Have you considered reducing from Dominating Set? Set weights =1, $K=k$ and $L=n-k$? Mar 18 '19 at 6:40
• @PålGD Yes, I considered the reduction function $f : \Sigma^* \rightarrow {\Sigma^*}'$ that transforms a Dominating Set ($\text{DS}$) problem instance to the above Weighted Vertices and Edges problem instance ($\text{WVE}$). Showing that $\forall x \in \text{DS} \rightarrow f(x) \in \text{WVE}$ is easy, just by setting the weights of the vertices to $1$ and the lengths of the edges to $1$, just like you said. However, I am having trouble proving that $\forall f(x) \in \text{WVE} \rightarrow x \in \text{DS}$. Mar 18 '19 at 10:11
• Oh actually, does that mean that I only have to consider transformed instances for the $\text{WVE}$ problem, which will always have vertex weights $1$ and edge lengths $1$? (so the example that I have given in the OP is actually useless?) Mar 18 '19 at 10:13
• If you can show that WVE is NP-hard even on unweighted graphs, that's a stronger statement, yes. Mar 18 '19 at 11:43

Given a graph $$G = (V, E)$$ and an integer $$k$$, is there a set $$V' \subseteq V$$ of size at most $$k$$ such that the distance of any vertex $$v \in V \setminus V'$$ to $$V'$$ is 1.
(This is assuming that the distance from $$v' \in V'$$ to $$V'$$ is defined as 0.)