Design-and-analysis-of-algorithms-max-cliques

DAA-最大クリーク

無向グラフでは、*クリーク*は与えられたグラフの完全な部分グラフです。 完全なサブグラフとは、このサブグラフのすべての頂点がこのサブグラフの他のすべての頂点に接続されていることを意味します。

最大クリーク問題は、グラフの最大クリークを見つける計算上の問題です。 マックスクリークは、多くの実世界の問題で使用されています。

頂点が人々のプロファイルを表し、エッジがグラフの相互の知人を表すソーシャルネットワーキングアプリケーションを考えてみましょう。 このグラフでは、クリークはすべてがお互いを知っている人々のサブセットを表します。

最大のクリークを見つけるには、すべてのサブセットを体系的に検査できますが、この種のブルートフォース検索は、数十以上の頂点を含むネットワークでは時間がかかりすぎます。

Algorithm: Max-Clique (G, n, k)
S := Φ
for i = 1 to k do
   t := choice (1…n)
   if t Є S then
      return failure
   S := S ∪ t
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do
   if (i, j) is not a edge of the graph then
      return failure
return success

分析

Max-Clique問題は非決定的なアルゴリズムです。 このアルゴリズムでは、最初に k 個の異なる頂点のセットを決定し、次にこれらの頂点が完全なグラフを形成するかどうかをテストします。

この問題を解決する多項式時間決定論的アルゴリズムはありません。 この問題はNP完全です。

例

次のグラフをご覧ください。 ここでは、頂点2、3、4、および6を含むサブグラフが完全なグラフを形成します。 したがって、このサブグラフは*クリーク*です。 これは提供されたグラフの最大の完全なサブグラフであるため、* 4-クリーク*です。

最大クリーク