Uma árvore de abrangência de um gráfico é chamada de árvore de completude se o conjunto de folhas induzir um subgráfico completo no gráfico do host. Dado um gráfico e um número inteiro , qual é a complexidade de decidir se contém uma árvore de completude com no máximo folhas?k G k
Uma razão para fazer essa pergunta é que o problema correspondente para árvores de independência é NP-completo; aqui, uma árvore de independência é uma árvore de abrangência, de modo que o conjunto de suas folhas é um conjunto independente no gráfico do host.
Outra razão é essa pergunta (e as respostas correspondentes). Acontece que toda árvore de abrangência de é uma árvore de completude se e somente se for um gráfico ou um ciclo completo. G
Não posso derrotar David na elegância de sua resposta. Mas, depois de gastar muito tempo pensando nesse problema, gostaria de trair minha solução para você;)
fonte