Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold Suppose we have a graph $G$ = ($V$, $E$) where each vertex $v_i \in V$ has a benefit $b_i$ and each edge ($v_i, v_j$) $\in E$ has a weight of $w_{ij}$. I would like to find a subgraph of $G$ that always contains the vertex $v_0 \in V$ and whose minimum spanning tree has the maximum sum of benefits with the restriction that the sum of the edge weights in the tree is less or equal to a threshold $T$. The formal definition of the problem is: 
max. $\sum_{v_i \in S} b_i$ s.t. $S \subseteq V$ and $v_0 \in S$ and $MSTCost(G, S) \leq T$ 
(Here, $MSTCost(G, S)$ returns the total weight cost of the minimum spanning tree of the vertices in $S$ within $G$.) 
As an example, say $V$ = $\{v_0, v_1, v_2\}$, $b_0$ = $b_1$ = $b_2$ = 1, $w_{01}$ = 5, $w_{02} = 1$, and $w_{12}$ = 1. If $T$ = 1, then the solution is $S$ = {$v_0$, $v_2$} with a total benefit of 2. If $T$ = 2, then the solution is $S$ = {$v_0, v_1, v_2$} with a total benefit of 3. 
Question: I can reduce the 0-1 Knapsack problem to the problem above, making it NP-hard. However, can the problem above be solved with dynamic programming in pseudo-polynomial time to $T$ as we can for the 0-1 Knapsack problem? 
 A: As is usual in complexity theory, we consider the decision version of your problem.
Instance: A graph G=(V,E), a vertex v0∈V, benefit bv∈ℕ for each vertex v, weight we∈ℕ for each edge e, T∈ℕ, and B∈ℕ.
Question: Is there a subset S⊆V which contains v0 such that the minimum spanning tree of the subgraph of G induced by S has weight at most T and the sum of the benefits of the vertices in S is at least B?
(By the way, this question can be equivalently stated as “Does G have a subtree J which contains v0 such that the sum of the benefits of the vertices in J is at least B and the sum of the weights of the edges in J is at most T?”  This wording may be simpler because it does not explicitly refer to the notion of minimum spanning tree.)
This problem is NP-complete in the strong sense, meaning that it is NP-complete even if all the numbers in the input are given in unary.  Therefore, your problem does not have a pseudo-polynomial-time algorithm unless P=NP.
The problem is clearly in NP.  To show the NP-hardness, I provide a reduction from the set cover problem to the aforementioned decision version.  (This reduction is similar to another reduction which I wrote on cstheory.stackexchange.com.)
Set cover
Instance: A finite set U, a family C of subsets of U, and k∈ℕ.
Question: Is there a cover D of U in C with at most k sets, that is, a subset D of C with |D|≤k such that the union of D is equal to U?
Given an instance (U, C, k) of the set cover problem, let U={a1, …, an} and C={S1, …, Sm} (n=|U|, m=|C|), and construct a graph G with three layers of vertices:


*

*The first layer consists of a single vertex v0 with benefit 0.

*The second layer consists of m vertices x1, …, xm with benefit 0, each of which has an edge from v0 with weight 1.

*The third layer consists of n vertices y1, …, yn with benefit 1.  Vertex yi has an edge from vertex xj with weight k+1 for each pair (i, j) such that ai∈Sj.


We claim that there is a cover of U in C with at most k sets if and only if the graph G has a subtree J which contains v0 such that the total benefit of J is at least n and the total weight of J is at most k+n(k+1), and therefore this transformation from the set cover problem to the current problem is indeed a reduction.  Note that if the graph G has such a subtree J, then J satisfies the following properties.


*

*J contains all of y1, …, yn.

*In J, vertices y1, …, yn are leaves (i.e., have degree 1).  (Otherwise the total weight would be at least (n+1)(k+1) > k+n(k+1).)


The aforementioned claim is easy to prove by using these properties.
