# np complete – Reducing subsetsum to \$L = { langle G, l, urangle | G text{ is a weighted graph that has a spanning tree with weight between \$l\$ and \$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 }$$.