Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold

Question

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?

Answer 1

As is usual in complexity theory, we consider the decision version of your problem.

Instance: A graph G=(V,E), a vertex v₀∈V, benefit b_v∈ℕ for each vertex v, weight w_e∈ℕ for each edge e, T∈ℕ, and B∈ℕ.
Question: Is there a subset S⊆V which contains v₀ 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 v₀ 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={a₁, …, a_n} and C={S₁, …, S_m} (n=|U|, m=|C|), and construct a graph G with three layers of vertices:

• The first layer consists of a single vertex v₀ with benefit 0.
• The second layer consists of m vertices x₁, …, x_m with benefit 0, each of which has an edge from v₀ with weight 1.
• The third layer consists of n vertices y₁, …, y_n with benefit 1. Vertex y_i has an edge from vertex x_j with weight k+1 for each pair (i, j) such that a_i∈S_j.

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 v₀ 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 y₁, …, y_n.
• In J, vertices y₁, …, y_n 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.