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
Actually that question (in particular this answer) is helpful.
A proof using cycle property:
Let $G=(V,E)$ be the original graph. Let the set of edges $T \subseteq E$ be a spanning tree on $G$ that is not minimum.
Now, there will exist an edge $e$ which belongs to the MST and not to $T$.
Adding $e$ it to $T$ creates a cycle. By cycle property, the most expensive edge of this cycle (call it $e'$) does not belong to the MST, so it must belong to $T$.
Removing $e'$ we break the cycle and we obtain a new subgraph $T'$ with lesser total weight than $T$. Furthermore, $T'$ is a spanning tree because:
So there must exist a spanning tree of lesser total weight, s.t. it differs from $T$ only by one edge.