無向グラフ G = G(V, E) が与えられた場合、多項式時間で最大のクリークのサイズを見つけるにはどうすればよいですか? エッジの数がわかれば、最大クリーク サイズに上限を設定できます。
https://cs.stackexchange.com/questions/11360/size-of-maximum-clique-given-a-fixed-amount-of-edges
、そしてその上限から 1 まで下向きに繰り返すことができます。この上限は O(sqrt(|E|)) であるため、O(sqrt(|E|) * sqrt で最大クリーク サイズを確認できると思います。 (|E|) * sqrt(|E|)) 時間。
この NP 完全問題をより効率的に解決する方法はありますか?
グラフ内で最大のクリークを見つけることは、グラフのクリーク数であり、最大クリーク問題 (MCP) としても知られています。これは、グラフ ドメインで最も深く研究されている問題の 1 つであり、NP 困難であることが知られているため、一般的なケースでそれを解決するための多項式時間アルゴリズムは見つからないと予想されます (多項式時間アルゴリズムを持つ特定のグラフ構成があります)。 ）。最大クリークを概算することさえ困難です (つまり、クリーク数に近い数を見つけます)。
正確な MCP アルゴリズムに関心がある場合は、過去 10 年間に多くの重要な改善が行われ、パフォーマンスが約 2 桁向上しました。現在主要なアルゴリズム ファミリは分枝限定型であり、近似色を使用して境界を計算します。最も重要なものと改善点を挙げます。
その他。実際、科学界では非常に活発な研究が行われています。現在、上位のアルゴリズムは BBMC、MCS であり、MaxSAT と言えます。これらのうち、おそらく BBMC とその亜種 (ビット文字列エンコーディングを使用) は、現在主要な汎用ソルバーです。BBMC に使用されるビット文字列のライブラリは公開されています。