<p>Similar to the solution for a binary tree, you can solve it in polynomial time on a tree without degree restriction:
First, generalize the problem such that every node also has a "count" $c_i\in\{0,1\}$, and the problem is to find a subforest $S$ of count $k=\sum_{i\in S} c_i$.
Generalize the dynamic programming approach to this version (it still works with a table, given a fixed count $C$, what is the minimal weight subforest in the subtree having count precisely $C$)  </p>

<p>Keep the original tree with nodes of count 1.  Every node $v$ with degree greater than 2 is split into a binary tree with deg$(v)$ leaves (the shape does not matter).  The new nodes have count and weight 0. Solve the problem on the new tree. When reading out the solution ignore any new node; this will still be a subforest of the same weight.  Because any original subforest translates into a new subforest of the same weight, the found subforest is optimal.</p>

CC BY-SA 2.5
2011-02-14T11:19:48.820Z
You have to adapt the parameter $k$ to get the equivalence of the optimal solutions.
Marc Bury
CC BY-SA 2.5
2011-02-14T11:27:23.587Z
Good point. I'll change my answer accordingly.
Riko Jacob
CC BY-SA 2.5
2011-02-14T10:04:12.723Z
2011-02-14T11:36:44.620Z
2011-02-14T11:36:44.620Z
Riko Jacob
<p>This question was motivated by a question asked on <a href="https://stackoverflow.com/questions/4898511/problem-bobs-sale">stackoverflow</a>.</p>

<p>Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$). </p>

<p>Each vertex $i$ has a non-negative integer weight associated: $w_i$.</p>

<p>Additionally, you are given an integer $k$, such that $1 \le k \le n$.</p>

<p>The weight $W(S)$ of a set of nodes $S \subseteq \{1,2,\dots, n\}$ is the sum of weights of the nodes: $\sum_{s \in S} w_s$.</p>

<blockquote>
  <p>Given input $T$, $w_i$ and $k$, </p>
  
  <p>The task is to find a <em>minimum</em> weight
  sub-forest* $S$, of $T$, such that $S$
  has exactly $k$ nodes (i.e. $|S| =
&gt; k$). </p>
  
  <p>In other words, for any subforest $S'$ of $T$, such that $|S'| = k$, we must have $W(S) \leq W(S')$.</p>
</blockquote>

<p>If the number of children of each node were bounded (for instance binary trees), then there is a polynomial time algorithm using dynamic programming.</p>

<p>I have a feeling that this is NP-Hard for general trees, but I haven't been able to find any references/proof. I even looked <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">here</a>, but could not find something which might help. I have feeling that this will remain NP-Hard even if you restrict $w_i \in \{0,1\}$ (and this might be easier to prove).</p>

<p>This seems like it should be a well studied problem. </p>

<blockquote>
  <p>Does anyone know if this is an NP-Hard problem/there is a known P time algorithm? </p>
</blockquote>

<hr>

<p>*A sub-forest of $T$ is a subset $S$ of nodes of the tree $T$, such that if $x \in S$, then all the children of $x$ are in $S$ too. (i.e. it is a disjoint union of rooted sub-trees of $T$).</p>

<p>PS: Please pardon me if it turns out that I missed something obvious and the question is really off-topic. </p>

CC BY-SA 2.5
2011-02-14T07:19:37.317Z
I strongly suspect this has an easy answer, but it's still a reasonable question.
Suresh Venkat
<cc.complexity-theory><reference-request><np-hardness><tree><application-of-theory>
Minimum weight subforest of given cardinality
Aryabhata
# Minimum weight subforest of given cardinality

(Asked by: username_0 on 2011-02-14)

This question was motivated by a question asked on [stackoverflow](https://stackoverflow.com/questions/4898511/problem-bobs-sale).

Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$).

Each vertex $i$ has a non-negative integer weight associated: $w\_i$.

Additionally, you are given an integer $k$, such that $1 \le k \le n$.

The weight $W(S)$ of a set of nodes $S \subseteq \{1,2,\dots, n\}$ is the sum of weights of the nodes: $\sum\_{s \in S} w\_s$.

> Given input $T$, $w\_i$ and $k$,
>
> The task is to find a *minimum* weight
> sub-forest\* $S$, of $T$, such that $S$
> has exactly $k$ nodes (i.e. $|S| =
> > k$).
>
> In other words, for any subforest $S'$ of $T$, such that $|S'| = k$, we must have $W(S) \leq W(S')$.

If the number of children of each node were bounded (for instance binary trees), then there is a polynomial time algorithm using dynamic programming.

I have a feeling that this is NP-Hard for general trees, but I haven't been able to find any references/proof. I even looked [here](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees), but could not find something which might help. I have feeling that this will remain NP-Hard even if you restrict $w\_i \in \{0,1\}$ (and this might be easier to prove).

This seems like it should be a well studied problem.

> Does anyone know if this is an NP-Hard problem/there is a known P time algorithm?

---

\*A sub-forest of $T$ is a subset $S$ of nodes of the tree $T$, such that if $x \in S$, then all the children of $x$ are in $S$ too. (i.e. it is a disjoint union of rooted sub-trees of $T$).

PS: Please pardon me if it turns out that I missed something obvious and the question is really off-topic.

**Tags:** cc.complexity-theory, reference-request, np-hardness, tree, application-of-theory
> **Comments:**
> **username_1**: I strongly suspect this has an easy answer, but it's still a reasonable question.  

---

## 1 answers

### Answer by username_2 on 2011-02-14. Score: 7 | Accepted answer

Similar to the solution for a binary tree, you can solve it in polynomial time on a tree without degree restriction:
First, generalize the problem such that every node also has a "count" $c\_i\in\{0,1\}$, and the problem is to find a subforest $S$ of count $k=\sum\_{i\in S} c\_i$.
Generalize the dynamic programming approach to this version (it still works with a table, given a fixed count $C$, what is the minimal weight subforest in the subtree having count precisely $C$)

Keep the original tree with nodes of count 1. Every node $v$ with degree greater than 2 is split into a binary tree with deg$(v)$ leaves (the shape does not matter). The new nodes have count and weight 0. Solve the problem on the new tree. When reading out the solution ignore any new node; this will still be a subforest of the same weight. Because any original subforest translates into a new subforest of the same weight, the found subforest is optimal.

> **Comments:**
> **username_3**: You have to adapt the parameter $k$ to get the equivalence of the optimal solutions.  
> **username_2**: Good point. I'll change my answer accordingly.  

---

