Le texte $ \ {k-key} problème $

Question

Étant donné un graphe non orienté, je définis une structure appelée k-clé comme un chemin contenant k $ sommets $ qui sont reliés à un cycle simple qui contient $ k sommets $ ainsi.

Voici le k-clé problème :. Donné un graphe non orienté $ G $ et un numéro $ k $, décider si $ G $ contient k $ k $ de -key

Je veux montrer que le problème de k-clé est une NP-complet.

Je veux faire une réduction du problème « hamiltonien Cycle non dirigé » dans lequel l'entrée est un graphique, et le problème est de décider si elle contient un chemin hamiltonien. Je sais déjà que ce problème est NP-complet. L'entrée de la réduction serait un graphe non orienté $ G $ et la sortie est un graphique de '$ G et $ k $. Pouvez-vous me aider à comprendre la manipulation que je dois faire le graphique d'origine afin de montrer cette réduction? Et pourquoi devrait-il fonctionner?

Answer 1

Vous voulez trouver un moyen de créer $ G '$ de $ G $ tel que $ G' $ a une touche k $ $ ssi $ G $ a un chemin hamiltonien.

Si un graphique $ G $ a $ k sommets $ et un chemin simple de longueur $ k $, alors que peut-on conclure à ce sujet ayant un chemin hamiltonien?

Je devine l'intention est que les sommets du chemin doit être différent des sommets du cycle (sinon chaque graphique du cycle de jambon contiendrait un k $ $ -key et vice versa). Donc, il suffit de penser, supposons que nous savions que $ G $ avait un cycle de jambon à partir de un sommet. Où serions-nous virer de bord sur certains sommets pour créer un G « $ qui avait une touche $ k $ en utilisant $ G $ » cycle de jambon s?