Subfloresta de peso mínimo de determinada cardinalidade

Esta pergunta foi motivada por uma pergunta no stackoverflow .

Suponha que você está dado uma árvore enraizada (ou seja, há uma raiz e nós ter filhos, etc.) em n nós (rotulados 1 , 2 , ... , n ).$T$$n$$1, 2, \dots, n$

Cada vértice tem um peso inteiro não negativo associado: w i .$i$$w_i$

Além disso, você recebe um número inteiro , de modo que 1 ≤ k ≤ n .$k$$1 \le k \le n$

O peso de um conjunto de nós S ⊆ { 1 , 2 , … , n } é a soma dos pesos dos nós: ∑ s ∈ S w s .$W(S)$$S \subseteq \{1,2,\dots, n\}$$\sum_{s \in S} w_s$

Dada a entrada , w i e k ,$T$$w_i$$k$

A tarefa é encontrar uma subfloresta de peso mínimo * , de T , de modo que S tenha exatamente k nós (ou seja, | S | = > k ).$S$$T$$S$$k$$|S| = > k$

Em outras palavras, para qualquer subfloresta de T , de modo que | S ' | = k , devemos ter W ( S ) ≤ W ( S ′ ) .$S'$$T$$|S'| = k$$W(S) \leq W(S')$

Se o número de filhos de cada nó foi limitado (por exemplo, árvores binárias), existe um algoritmo de tempo polinomial usando programação dinâmica.

Sinto que isso é NP-Hard para árvores em geral, mas não consegui encontrar nenhuma referência / prova. Eu até olhei aqui , mas não consegui encontrar algo que pudesse ajudar. Sinto que isso permanecerá NP-Difícil, mesmo se você restringir (e isso pode ser mais fácil de provar).$w_i \in \{0,1\}$

Parece que deve ser um problema bem estudado.

Alguém sabe se este é um problema NP-Hard / se existe um algoritmo de tempo P conhecido?

* Um sub-bosque de é um subconjunto S de nós da árvore T , tal que se x ∈ S , em seguida, todos os filhos de x estão em S também. (isto é, é uma união disjunta de subárvores enraizadas de T ).$T$$S$$T$$x \in S$$x$$S$$T$

PS: Por favor, perdoe-me se eu perdi algo óbvio e a pergunta é realmente fora de tópico.

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

$v$$(v)$