algorithm - グラフのクリーク数

Question

約100個の頂点を持つグラフのクリーク数のみ（実際にはクリークを検出せずに）を検出する高速アルゴリズムを知りたいです。

私は次の問題を解決しようとしています。 http://uva.onlinejudge.org/external/1/193.html

Answer 1

これは NP 完全であり、実際に最大クリークを見つけてその頂点を数えることよりもはるかに優れた方法はありません。ウィキペディアから：

クリークの問題には次のものがあります。

• グラフに N より大きいクリークが含まれているかどうかをテストする決定問題を解く

これらの問題はすべて難しいです: クリーク決定問題は -完全NP(Karp の 21 の-NP完全問題の 1 つ)、

でクリーク数を見つけることができればP、決定問題は で答えられPます (クリーク数を計算して と比較するだけですN)。

決定問題はNP-Completeであるため、一般グラフのクリーク数を求めると、 になりますNP-Hard。

Answer 2

他の人がすでに述べたように、これはおそらく本当に難しいです。

しかし、多くの理論的に困難な問題と同様に、優れたアルゴリズムと適切なデータを使用すると、実際にはかなり高速になります。これまでに見つけた最大のクリーク サイズを追跡しながら、クリークを見つけるために Bron-Kerbosch のようなものを実装すると、無駄な検索ツリーからバックトラックできます。

たとえば、20 個のノードを含むクリークが見つかり、次数が 20 未満のノードがネットワークに多数ある場合、それらのノードを以降の検討からすぐに除外できます。一方、次数分布がより均一である場合、これはすべてのクリークを見つけるのと同じくらい遅くなる可能性があります。