2
$\begingroup$

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$:

enter image description here

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?

$\endgroup$
4
  • 1
    $\begingroup$ Why doesn't it work? Have you considered reducing from Dominating Set? Set weights =1, $K=k$ and $L=n-k$? $\endgroup$
    – Pål GD
    Mar 18, 2019 at 6:40
  • $\begingroup$ @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}$. $\endgroup$
    – Adnan
    Mar 18, 2019 at 10:11
  • $\begingroup$ 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?) $\endgroup$
    – Adnan
    Mar 18, 2019 at 10:13
  • 1
    $\begingroup$ If you can show that WVE is NP-hard even on unweighted graphs, that's a stronger statement, yes. $\endgroup$
    – Pål GD
    Mar 18, 2019 at 11:43

1 Answer 1

Reset to default
1
$\begingroup$

This problem is a generalization of Dominating Set, and if you let weights of vertices and edges be 1, then you have exactly Dominating Set.

The problem definition of Dominating Set is:

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.)

It follows that WVE is NP-hard. This is occasionally called proof by generalization.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.