algorithm - 多項式時間で最大クリークの頂点を見つける

Question

クリーク問題を一定時間で解決するブラック ボックスが与えられたとします。

ブラック ボックスに境界 k を持つ無向グラフ G を与えると、グラフ G が少なくとも k 個の頂点を持つクリークを持っていることを「はい」または「いいえ」のいずれかで出力します。

多項式時間で最大クリークの頂点を見つけるために、このブラック ボックスをどのように使用しますか?

Answer 1

ヒントとして、グラフからノードを選択して削除し、k クリークがまだ存在するかどうかを確認するとどうなるかを考えてみてください。ブラックボックスは、存在するか存在しないかのいずれかを示します。k クリークがまだ存在する場合、何を学びますか? ない場合、何を学びますか？

お役に立てれば！