Subfloresta de peso mínimo de determinada cardinalidade

11

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

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

Além disso, você recebe um número inteiro , de modo que 1 k n .k1kn

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{1,2,,n}sSws

Dada a entrada , w i e k ,Twik

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

Em outras palavras, para qualquer subfloresta de T , de modo que | S ' | = k , devemos ter W ( S ) W ( S ) .ST|S|=kW(S)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).wi{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 ).TSTxSxST

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

Aryabhata
fonte
Eu suspeito fortemente que isso tenha uma resposta fácil, mas ainda é uma pergunta razoável.
Suresh Venkat

Respostas:

7

ci{0,1}Sk=iSciCC

v(v)

Riko Jacob
fonte
k
Bom ponto. Vou mudar minha resposta de acordo.
Riko Jacob