Peso mínimo subforest de cardinalidad dada

Esta pregunta fue motivada por una pregunta hecha en stackoverflow .

Supongamos que se le da un árbol enraizado (es decir, hay una raíz y los nodos tienen hijos, etc.) en n nodos (etiquetados 1 , 2 , ... , n ).$T$$n$$1, 2, \dots, n$

Cada vértice tiene un peso entero no negativo asociado: w i .$i$$w_i$

Además, se le da un número entero , tal que 1 ≤ k ≤ n .$k$$1 \le k \le n$

El peso de un conjunto de nodos S ⊆ { 1 , 2 , ... , n } es la suma de los pesos de los nodos: ∑ s ∈ S w s .$W(S)$$S \subseteq \{1,2,\dots, n\}$$\sum_{s \in S} w_s$

Dada la entrada , w i y k ,$T$$w_i$$k$

La tarea es encontrar un sub-bosque de peso mínimo * , de T , de modo que S tenga exactamente k nodos (es decir, | S | = > k ).$S$$T$$S$$k$$|S| = > k$

En otras palabras, para cualquier subforest de T , tal que | S ′ | = k , debemos tener W ( S ) ≤ W ( S ′ ) .$S'$$T$$|S'| = k$$W(S) \leq W(S')$

Si el número de hijos de cada nodo estaba limitado (por ejemplo, árboles binarios), entonces hay un algoritmo de tiempo polinómico que usa programación dinámica.

$w_i \in \{0,1\}$

Parece que debería ser un problema bien estudiado.

¿Alguien sabe si este es un problema NP-Hard / hay un algoritmo de tiempo P conocido?

$T$$S$$T$$x \in S$$x$$S$$T$

PD: Disculpe si resulta que me perdí algo obvio y la pregunta está realmente fuera de tema.

$c_i\in\{0,1\}$$S$$k=\sum_{i\in S} c_i$$C$$C$

$v$$(v)$