0
$\begingroup$

The node weighted Steiner Tree Problem as found in this compendium:

$\textbf{Instance}: \text{Graph } G = (V, E)\text{, set of terminals } S \subseteq V \text{ and a node weight function } w:V \to \mathbb{R}^+$
$\textbf{Solution}: \text{A tree } T = (V_T,E_T) \text{ in } G \text{, such that } S\subseteq V_T \subseteq V,~E_T \subseteq E.$
$\textbf{Objective}: \text{Minimize the sum of the vertices weight}$

Is NP hard. But what if all nodes have the same weight? So the weight function $w$ is just a constant function that maps to 1 for all Vertices: $\forall v \in V:w(v) = 1$

Is there a name for this Problem? Is it NP hard? If yes what algorithms can I use for approximation?

Please note that this problem is not equals MST, ShortestPath or TSP

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Since all vertex weights are equal, minimizing $\sum_{v \in V_T} w(v)$ is equivalent to minimizing $|V_T|$, and since a tree on $x$ vertices has exactly $x-1$, edges, this is equivalent to minimizing $|E_T|$.

Therefore your problem is NP-hard.

Moreover, any $\alpha$-approximation algorithm for the classical Steiner tree problem, where $\alpha$ is a constant, can also be used to provide a $\alpha$-approximation for your version. Let $v$ be a terminal and let $\overline{w}$ be the (constant) vertex weight. Add a new vertex $v'$ and the edge $(v, v')$. Then drop all vertex weights, and set all edge weights to $\overline{w}$.

You are left with an instance of Steiner tree such that any solution to this instance can be converted to a solution for your version of the problem having the same cost (by simply deleting $(v,v')$ from $T_V$), and vice-versa (by adding $(v,v')$ to $T_V$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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