# Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u} [duplicate]

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

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 \}$$.