-2
$\begingroup$

How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below?

input : a weighted graph $G$ and numbers $l$ and $u$.
output : Does $G$ has spanning tree, $S$, such that $l \leq \mathrm{weight}(S) \leq u$?

$\endgroup$
1
0
$\begingroup$

Let $X = \{ x_1, x_2, \dots, x_n \}$ be the (multi-)set of elements in your subset-sum instance and let $t$ be the target value.

Create the undirected graph $G=(V,E)$ where $V=\{a,b\} \cup X$ and $E = ( \{a,b\} \times X) \cup \{(a,b)\}$. The weight of edge $(a, x_i)$, for $x_i \in X$, is $x_i$. The weight of edge $(b, z)$ for $z \in \{a\} \cup X$ is $0$. Finally, pick $l=u=t$.

There is some $Y \subset X$ such that $\sum_{x_i \in Y} x_i = t$ if and only if there is a spanning tree $T$ of $G$ of total weight between $l$ and $u$.

Indeed, given $Y$, you can select $T$ as the tree induced by the edges in $\{(a,x_i) \mid x_i \in Y\} \cup \{(b,z) \mid z \in V \setminus Y\}$. Moreover, given a tree $T=(V,F)$ of total weight between $l$ and $u$, you can select $Y = \{ x_i \mid (a,x_i) \in F \}$.

$\endgroup$