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?

  • $\begingroup$ “I would like to find a minimum spanning tree” That is wrong according to your description of the problem following that part. What you want to find is a subset S⊆V. $\endgroup$ – Tsuyoshi Ito Oct 5 '11 at 10:42
  • $\begingroup$ Thanks Tsuyoshi, I fixed the problem statement. $\endgroup$ – Steven Oct 5 '11 at 11:22
  • $\begingroup$ Thank you for fixing it. I realized another typo: the formal definition mentions c_0, but it is probably a typo for v_0. $\endgroup$ – Tsuyoshi Ito Oct 5 '11 at 11:33
  • $\begingroup$ Thanks, I changed c_0 to v_0. $\endgroup$ – Steven Oct 5 '11 at 20:44

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

Instance: A graph G=(V,E), a vertex v0V, benefit bv∈ℕ for each vertex v, weight we∈ℕ for each edge e, T∈ℕ, and B∈ℕ.
Question: Is there a subset SV 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 aiSj.

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.

  • $\begingroup$ Thanks for the elegant proof. Since the Set Cover problem is strongly NP-complete, I can see that my problem is also strongly NP-complete. I wonder if there is no hope for dynamic programming algorithm then? :( $\endgroup$ – Steven Oct 5 '11 at 21:32
  • $\begingroup$ @Steven: As long as you want an exact algorithm which works for all instances of your problem, there is no hope (unless you can prove P=NP ☺). Typical ways to cope with NP-completeness are (1) try exponential-time algorithms if your instances are small enough, (2) give up solving all the instances and try to find specific structures in instances you want to solve, and (3) consider approximation algorithms. A gentle introduction to them can be found in Garey and Johnson. $\endgroup$ – Tsuyoshi Ito Oct 5 '11 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.