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.
(1) is true iff $G=K_2$. (although, maybe empty graph and $K_1$ would trivially satisfy this?)
(2) would be true if, say, $G$ is a tree with at least two edges.
(3) I do not think could ever be true. Two different spanning trees would mean $G$ has at least two edges, and the sum of squares of at least two numbers $\geq 1$ is never equal to the square of the sum.
I'm not sure how you should answer the question, but that's my understanding of the problem.
Best Answer
Let the two sets of vertices be $X$ and $Y$. If the equality subgraph does not have a perfect matching, it must violate Hall’s marriage condition, so there is some $X'\subseteq X$ adjacent to fewer than $|X'|$ vertices in $Y$. Let $Y'$ be the set of vertices in $Y$ adjacent to $X'$ in the equality subgraph. The adjustment to the cover consists in replacing $u_k$ by $u_k-\alpha$ for each $x_k\in X'$ and $v_k$ by $v_k+\alpha$ for each $y_k\in Y'$, where $\alpha=\min\{u_k+v_j-\operatorname{wt}(x_ky_j):u_k\in X'\text{ and }y_j\in Y'\}$. The net change in the cost of the cover is therefore $\left(-|U'|+|V'|\right)\alpha<0$, and the cost of the new cover is therefore less than the cost of the old.
This PDF has a presentation that I think is slightly different from the one that you have in mind; it arrives at the optimality by a different route that may be easier to follow, especially with the nice example at the end.