Por que o problema da árvore de extensão delimitada por k é NP-completo?

12

O problema da árvore de abrangência ligada a é onde você tem um gráfico não direcionado G ( V , E ) e você precisa decidir se ela tem ou não uma árvore de abrangência, de modo que cada vértice tenha um grau de no máximo k .kG(V,E)k

Percebo que, para o caso , esse é o problema do caminho hamiltoniano. No entanto, estou tendo problemas com casos em que k > 2 . Tentei pensar sobre isso no sentido de que você pode adicionar mais nós a uma árvore de abrangência existente em que k = 2 e, talvez, como a base seja NP completa, adicionar coisas o tornará NP completo também, mas isso não parece certo. Eu sou autodidata em CS e estou tendo problemas com a teoria, então qualquer ajuda será apreciada!k=2k>2k=2

user17199
fonte

Respostas:

9

A pergunta já foi feita antes no stackoverflow , onde também foi respondida. A idéia é conectar cada vértice a novos vértices. O novo gráfico possui uma árvore de abrangência vinculada a k se o gráfico original tiver um caminho hamiltoniano.k-2k

(k+1)k1

Yuval Filmus
fonte
1

Meu entendimento é que, se você possui um algoritmo que pode resolver o problema da árvore de abrangência limitada por k com qualquer k, pode usar esse algoritmo para resolver um caso especial com k = 2, que é essencialmente um caminho hamiltoniano. Portanto, se seu algoritmo pode atingir o tempo polinomial, ele pode ser usado para resolver o caminho de Hamilton no tempo polinomial, o que equivale a resolver qualquer problema np-complete em tempo polinomial. Portanto, o problema da árvore estendida com limite de k deve ser np-complete. Observe que essa é uma ideia geral, não uma prova completa.

Observe também que ser np-complete não significa que não haja algoritmos de tempo polinomial que possam resolver o problema. Ninguém provou isso ainda. Isso significa apenas que todos os problemas que são np-complete são igualmente difíceis e se um pode ser resolvido no tempo polinomial, todos podem ser resolvidos no tempo polinomial.

Sam G
fonte