Minimalna waga lasy o podanej liczności

11

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 , , nT.n1,2),,n

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

Dodatkowo podana jest liczba całkowita , taka jak .1 k nk1kn

Waga zestawu węzłów jest sumą wag węzłów: .S { 1 , 2 , , n } s S w sW.(S.)S.{1,2),,n}sS.ws

Biorąc pod uwagę dane wejściowe , i ,w i kT.wjak

Zadaniem jest znalezienie minimalnej masy sub-las * , Z , tak że ma dokładnie węzłów (tj ).T SS.T.S.| S | = > kk|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.|=kW.(S.)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).wja{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 TT.S.TxS.xS.T.

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

Aryabhata
źródło
Podejrzewam, że ma to łatwą odpowiedź, ale wciąż jest to rozsądne pytanie.
Suresh Venkat

Odpowiedzi:

7

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 Cdoja{0,1}S.k=jaS.dojadodo

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)

Riko Jacob
źródło
Musisz dostosować parametr aby uzyskać równoważność optymalnych rozwiązań. k
Marc Bury,
Słuszna uwaga. Zmienię odpowiednio swoją odpowiedź.
Riko Jacob