Minimalna waga lasy o podanej liczności

To pytanie było motywowane pytaniem dotyczącym przepływu stosu .

Załóżmy, że otrzymujesz zrootowane drzewo (tzn. Jest to root, a węzły mają dzieci itp.) W węzłach (oznaczonych ).n 1 , 2 , … , $T$$n$$1, 2, \dots, n$

Każdy wierzchołek ma powiązaną nieujemną masę całkowitą: .w $i$$w_i$

Dodatkowo podana jest liczba całkowita , taka jak .1 ≤ k ≤ $k$$1 \le k \le n$

Waga zestawu węzłów jest sumą wag węzłów: .S ⊆ { 1 , 2 , … , n } ∑ s ∈ S w $W(S)$$S \subseteq \{1,2,\dots, n\}$$\sum_{s \in S} w_s$

Biorąc pod uwagę dane wejściowe , i ,w i$T$$w_i$$k$

Zadaniem jest znalezienie minimalnej masy sub-las * , Z , tak że ma dokładnie węzłów (tj ).T $S$$T$$S$| S | = > $k$$|S| = > k$

Innymi słowy, dla dowolnego lasu leśnego z , takiego jak , musimy mieć . T | S ′ | = k W ( S ) ≤ W ( S ′$S'$$T$$|S'| = k$$W(S) \leq W(S')$

Jeśli liczba potomków każdego węzła została ograniczona (na przykład drzewa binarne), wówczas istnieje algorytm wielomianowy wykorzystujący programowanie dynamiczne.

Mam wrażenie, że jest to NP-Hard dla ogólnych drzew, ale nie znalazłem żadnych referencji / dowodów. Patrzyłem nawet tutaj , ale nie mogłem znaleźć czegoś, co mogłoby pomóc. Mam wrażenie, że pozostanie NP-Hard, nawet jeśli ograniczysz (i może to być łatwiejsze do udowodnienia).$w_i \in \{0,1\}$

Wydaje się, że powinien to być dobrze zbadany problem.

Czy ktoś wie, czy jest to trudny problem NP / czy istnieje znany algorytm czasu P.

* Sub-las jest podzbiorem węzłów drzewa , tak, że jeśli , to wszystkie dzieci są w też. (tj. jest to rozłączny związek ukorzenionych podgrzewań ).S T x ∈ S x S $T$$S$$T$$x \in S$$x$$S$$T$

PS: Proszę mi wybaczyć, jeśli okaże się, że coś przeoczyłem, a pytanie jest naprawdę nie na temat.

Podobnie do rozwiązania dla drzewa binarnego, możesz rozwiązać go w czasie wielomianowym na drzewie bez ograniczenia stopnia: Najpierw problem tak, że każdy węzeł ma również „liczbę” i problem polega na znalezieniu pod lasu leśnego o liczbie . Uogólnij podejście do programowania dynamicznego dla tej wersji (nadal działa z tabelą, biorąc pod uwagę stałą liczbę , jaka jest minimalna waga lasu podrzędnego w poddrzewie, mając liczbę dokładnie ) S k = ∑ i ∈ S c i C $c_i\in\{0,1\}$$S$$k=\sum_{i\in S} c_i$$C$$C$

Zachowaj oryginalne drzewo z węzłami liczenia 1. Każdy węzeł o stopniu większym niż 2 jest podzielony na drzewo binarne z liśćmi deg (kształt nie ma znaczenia). Nowe węzły mają liczbę i wagę 0. Rozwiąż problem na nowym drzewie. Podczas odczytywania rozwiązania zignoruj ​​nowy węzeł; nadal będzie to las o tej samej wadze. Ponieważ każdy pierwotny las leśny przekłada się na nowy las leśny o tej samej masie, znaleziony las leśny jest optymalny.( v $v$$(v)$