「G がサイズ k のクリークとサイズ k の独立集合の両方を持っているかどうか、与えられた入力 G と k を決定することが NP-Complete であることを証明してください。これは 2 ではなく 1 つの問題であることに注意してください。答えは、次の場合にのみ「はい」です。 G にはこれらのサブセットの両方があります。」
この問題は私のアルゴリズム コースで出されましたが、大勢の学生がそれを理解できませんでした。ここに私たちがこれまでに持っているものがあります...
クリーク問題と独立集合問題の両方が、それ自体で NP 完全であることはわかっています。いくつかの「証明書」がNPにある場合、この問題の検証が行われることもわかっています。
この問題は、上記の問題 (独立集合とクリークの両方を含む) を、完全にクリークまたは独立集合で構成される問題のいずれかに縮約することです (少なくとも、それは私たちが行う必要があると考えていることです)。リダクションを元の形式に戻すために必要な情報を失うことなく、このリダクションを実行する方法はわかりません。
ヒント：いくつかの頂点を追加して、CLIQUEをこの問題に減らします。
ヒントをくれた「Moron」と「RafalDowgird」に感謝します！それに基づいて、私は解決策を持っていると思います。私が間違っている場合は私を訂正してください：
クリークと独立集合の問題がNP完全であることはすでにわかっているので、それを問題を証明するための基礎として使用できます。私たちの問題をコンビネーションクリーク独立集合問題（CCIS）と呼びましょう。
サイズkのクリークCを持つグラフGが与えられたと仮定します。このグラフを、Cの各頂点にk個の頂点を付加することにより、サイズk'のクリークC'とサイズk'の独立集合Iの両方を持つグラフG'（読み取り：Gプライム）に縮小できます。この縮小は、頂点の追加からの多項式時間はO（n * k）時間かかります（グラフ内のn個の頂点と各ノードに接続されたk個の頂点）。
C =C'およびk=k'であることに注意してください。
ここで、サイズk'のクリークC'とサイズk'の独立集合Iを持つグラフG'が与えられ、これが真であると判断されたとします。クリークのみを見つけるためにグラフを変更する必要がないため、クリーク問題への還元は簡単です。