algorithm - グラフの独立集合

Question

ご存じのように、最大​​独立集合を見つけることは NP です。特定のグラフに少なくとも k 個の頂点の独立したセットがあるかどうかを調べるアルゴリズムはありますか? 見つけたくないことに注意してください。そのようなものが存在するかどうかを知りたいだけです。

Answer 1

ウィキペディアの引用：

独立集合決定問題では、入力は無向グラフと数値kであり、出力はブール値です。グラフにサイズkの独立集合が含まれる場合は true、そうでない場合は false です。

この問題は NP 完全です。グラフには、正確にk個の頂点の独立したセットがある場合にのみ、少なくともk個の頂点の独立したセットがあるため、あなたの問題は同じ質問をします。

つまり、あなたの問題もNP完全です。