$ text {k-key} $の問題

Question

無向グラフが与えられた場合、私は呼ばれる構造を定義します Kキー $ k $の頂点にも接続された$ k $頂点を含むパスとして。

これが次のとおりです Kキーの問題: ：無向グラフ$ g $と数字$ k $を与えられている場合、$ g $がK $ k $ -Keyが含まれているかどうかを決定します。

Kキーの問題がNP完全であることを示したいと思います。

入力がグラフである「無向ハミルトニアンサイクル」問題から削減したいのですが、問題はハミルトニアンの経路が含まれているかどうかを決定することです。この問題がNP完全であることをすでに知っています。削減の入力は無向グラフ$ g $であり、出力は$ g '$グラフと$ k $です。この削減を示すために、元のグラフに対してどのような操作をすべきかを理解するのを手伝ってください。そして、なぜそれが機能する必要があるのですか？

Answer 1

$ g '$が$ k $ -key iff $ g $にハミルトニアンパスがあるように、$ g $から$ g $を作成する方法を見つけたいと思います。

グラフ$ g $に$ k $頂点と長さの$ k $の単純なパスがある場合、ハミルトニアンパスを持っていることについて何を結論付けることができますか？

私は、パス内の頂点はサイクルの頂点とは異なる必要があるという意図があると推測しています（そうでなければ、すべてのハムサイクルグラフには$ k $ -Keyが含まれ、その逆も含まれます）。だから、$ g $が頂点から始まるハムサイクルがあることがわかっていたとしましょう。いくつかの頂点をどこにタックして、$ g $のハムサイクルを使用して$ k $ keyを備えた$ g '$を作成しますか？