Pourquoi le problème du spanning tree lié à k est-il NP-complet?

Le problème de l'arbre couvrant délimité par est celui où vous avez un graphe non orienté et vous devez décider s'il a ou non un arbre couvrant tel que chaque sommet a un degré d'au plus .G ( V , E ) $k$$G(V,E)$$k$

Je me rends compte que pour le cas , c'est le problème du chemin hamiltonien. Cependant, j'ai des problèmes avec les cas où . J'ai essayé d'y penser dans le sens où vous pouvez ajouter plus de nœuds sur un arbre couvrant existant où et peut-être puisque la base est NP complète, l'ajout de choses le rendra également NP-complet, mais cela ne semble pas droite. Je suis CS autodidacte et j'ai des problèmes avec la théorie, donc toute aide sera appréciée!k > 2 k = $k=2$$k>2$$k=2$

La question a déjà été posée sur stackoverflow , où il a également été répondu. L'idée est de connecter chaque sommet à nouveaux sommets. Le nouveau graphique a un arbre couvrant borné si le graphique d'origine a un chemin hamiltonien.$k-2$$k$

Mohit Singh et Lap Chi Lau ont donné un algorithme de polytime qui trouve un arbre couvrant délimité s'il existe un arbre couvrant délimité . Nous pouvons donc déterminer le degré minimum d'un arbre couvrant jusqu'à une incertitude de .k $(k+1)$$k$$1$

Ma compréhension est que si vous avez un algorithme qui peut résoudre le problème de l'arbre couvrant avec k avec n'importe quel k, vous pouvez utiliser cet algorithme pour résoudre un cas spécial avec k = 2, qui est essentiellement un chemin hamiltonien. Donc, si votre algorithme peut atteindre le temps polynomial, il peut être utilisé pour résoudre le chemin de Hamilton en temps polynomial, ce qui équivaut à résoudre tout problème np-complet en temps polynomial. Ainsi, le problème du spanning tree lié à k doit être np-complet. Notez que c'est une idée générale, pas une preuve complète.

Notez également qu'être np-complet ne signifie pas qu'aucun algorithme de temps polynomial ne peut résoudre le problème. Personne ne l'a encore prouvé. Cela signifie seulement que tous les problèmes qui sont np-complets sont également difficiles et si l'un peut être résolu en temps polynomial, alors tous peuvent être résolus en temps polynomial.