Sous-forêt de poids minimum de cardinalité donnée

Cette question était motivée par une question posée sur stackoverflow .

Supposons que l'on vous donne un arbre enraciné (c'est-à-dire qu'il y a une racine et que les nœuds ont des enfants, etc.) sur n nœuds (étiquetés 1 , 2 , … , n ).$T$$n$$1, 2, \dots, n$

Chaque sommet a un poids entier non négatif associé: w i .$i$$w_i$

De plus, on vous donne un entier , tel que 1 ≤ k ≤ n .$k$$1 \le k \le n$

Le poids d'un ensemble de nœuds S ⊆ { 1 , 2 , … , n } est la somme des poids des nœuds: ∑ s ∈ S w s .$W(S)$$S \subseteq \{1,2,\dots, n\}$$\sum_{s \in S} w_s$

Étant donné l'entrée , w i et k ,$T$$w_i$$k$

La tâche consiste à trouver une sous-forêt de poids minimum * , de T , telle que S ait exactement k nœuds (ie | S | = > k ).$S$$T$$S$$k$$|S| = > k$

En d'autres termes, pour toute sous-forêt de T , telle que | S ′ | = k , nous devons avoir W ( S ) ≤ W ( S ′ ) .$S'$$T$$|S'| = k$$W(S) \leq W(S')$

Si le nombre d'enfants de chaque nœud était borné (par exemple les arbres binaires), il existe alors un algorithme polynomial temporel utilisant la programmation dynamique.

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

Cela semble être un problème bien étudié.

Est-ce que quelqu'un sait s'il s'agit d'un problème NP-Hard / existe-t-il un algorithme de temps P connu?

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

PS: Veuillez m'excuser s'il s'avère que j'ai raté quelque chose d'évident et que la question est vraiment hors sujet.

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

$v$$(v)$