Loading article…
コンピュータサイエンスにおいて、クリーク問題とは、グラフ内のクリーク（互いに隣接する頂点のサブセットで、完全部分グラフとも呼ばれる）を見つける計算問題です。どのクリークを見つけるか、またクリークに関するどのような情報を見つけるかによって、いくつかの異なる定式化があります。クリーク問題の一般的な定式化には、最大クリーク（可能な限り最大の頂点数を持つクリーク）を見つけること、重み付きグラフで最大重みクリークを見つけること、すべての最大クリーク（拡大できないクリーク）を列挙すること、そしてグラフに指定されたサイズよりも大きなクリークが含まれているかどうかを判定する決定問題を解くことなどがあります。
クリーク問題は、次のような現実世界の状況で発生します。グラフの頂点が人を表し、辺が相互の知り合いを表すソーシャルネットワークを考えてみましょう。クリークとは、全員がお互いを知っている人々のサブセットを表し、クリークを見つけるアルゴリズムを使用して、このような共通の友人のグループを見つけることができます。クリーク問題は、ソーシャルネットワークへの応用だけでなく、バイオインフォマティクスや計算化学にも多くの応用例があります。
クリーク問題のほとんどのバージョンは困難である。クリーク決定問題はNP完全問題である（カープが挙げた21のNP完全問題の1つ）。最大クリークを見つける問題は、固定パラメータでは扱いが難しく、近似も困難である。また、最大クリークを指数関数的に多く持つグラフが存在するため、すべての最大クリークを列挙するには指数関数的な時間が必要になる可能性がある。したがって、クリーク問題に関する理論の多くは、より効率的なアルゴリズムが適用可能な特殊なタイプのグラフを特定すること、またはさまざまな計算モデルにおける一般問題の計算上の困難性を確立することに費やされている。
最大クリークを見つけるには、すべての部分集合を系統的に調べる方法がありますが、このような総当たり探索は、数十個を超える頂点を持つネットワークでは時間がかかりすぎて実用的ではありません。この問題に対する多項式時間アルゴリズムは知られていませんが、総当たり探索よりも効率的なアルゴリズムは知られています。例えば、Bron–Kerboschアルゴリズムを使用すると、最悪の場合でも最適な時間ですべての最大クリークを列挙でき、クリークごとに多項式時間で列挙することも可能です。
数学における完全部分グラフの研究は、「クリーク」という用語よりも古い。例えば、完全部分グラフは、エルデシュとセケレス (1935)によるラムゼー理論のグラフ理論的再定式化において、数学文献に早くから登場している。しかし、「クリーク」という用語と、クリークをアルゴリズム的に列挙するという問題は、どちらも社会科学に由来する。社会科学では、完全部分グラフは、互いに知り合いのグループである社会的クリークをモデル化するために使用されている。ルースとペリー (1949) は、グラフを使用してソーシャル ネットワークをモデル化し、社会科学の用語をグラフ理論に適用した。彼らは、完全部分グラフを「クリーク」と呼んだ最初の人物である。クリーク問題を解決するための最初のアルゴリズムは、社会学的な応用に着想を得たハラリーとロス (1957) [ 1 ]によるものである。社会科学の研究者たちは、ソーシャルネットワークにおけるさまざまなタイプのクリークや最大クリーク、つまりネットワーク内の人々やアクターの「結束力のあるサブグループ」を定義してきました。これらのサブグループは、いくつかの異なる種類の接続関係のいずれかを共有しています。クリークに関するこれらの一般化された概念の多くは、エッジがソーシャルネットワーク内の関連するアクターのペアを表す無向グラフを構築し、そのグラフにクリーク問題のアルゴリズムを適用することによっても見つけることができます。[ 2 ]
ハラリーとロスの研究以来、多くの人々がクリーク問題のさまざまなバージョンに対するアルゴリズムを考案してきた。[ 1 ] 1970年代には、研究者たちは最悪ケース分析の観点からこれらのアルゴリズムの研究を始めた。例えば、最大クリーク問題の最悪ケース複雑性に関する初期の研究であるタージャンとトロヤノフスキー（1977）を参照。また、1970年代には、クック（1971）とカープ（1972）の研究を皮切りに、研究者たちはNP完全性の理論と関連する難解性の結果を用いて、クリーク問題の難しさに対する数学的な説明を提供し始めた。1990年代には、ファイゲら（1991）を皮切りとする画期的な一連の論文により、 （ P ≠ NPを仮定すると）この問題を正確かつ効率的に近似することさえ不可能であることが示された。
クリーク探索アルゴリズムは、化学において、標的構造に一致する化学物質を見つけるため[ 3 ]、および分子ドッキングや化学反応の結合部位をモデル化するために使用されてきました[ 4 ]。また、異なる分子内の類似構造を見つけるためにも使用できます[ 5 ] 。これらのアプリケーションでは、各頂点が2つの分子からそれぞれ1つずつ、一致する原子のペアを表すグラフを作成します。2つの頂点は、それらが表す一致が互いに互換性がある場合にエッジで接続されます。互換性があるとは、たとえば、2つの分子内の原子間の距離が、ある許容範囲内でほぼ等しいことを意味する場合があります。このグラフのクリークは、すべての一致が互いに互換性のある原子のペアの集合を表します[ 6 ] 。この方法の特殊なケースは、グラフのモジュラー積を使用して、 2つのグラフの最大共通誘導部分グラフを見つける問題を、それらの積で最大クリークを見つける問題に還元することです[ 7 ] 。
自動テストパターン生成では、クリークを見つけることでテストセットのサイズを制限することができます。[ 8 ]バイオインフォマティクスでは、クリーク発見アルゴリズムは進化系統樹の推論[ 9 ] 、タンパク質構造の予測[ 10 ]、および密接に相互作用するタンパク質のクラスターの発見[ 11 ]に使用されています。依存関係グラフ内のクリークをリストすることは、特定のランダムプロセスの分析における重要なステップです。[ 12 ]数学では、ハイパーキューブの面対面タイリングに関するケラーの予想は、関連グラフ上でクリーク発見アルゴリズムを使用して反例を見つけたラガリアスとショール（1992）によって反証されました。 [ 13 ]
無向グラフは、有限個の頂点の集合と、エッジと呼ばれる頂点の順序付けされていないペアの集合によって構成されます。慣例として、アルゴリズム解析では、グラフの頂点の数はnで表され、エッジの数はmで表されます。グラフGのクリークは、 Gの完全部分グラフです。つまり、Kの任意の 2 つの頂点がGのエッジの 2 つの端点となるような頂点の部分集合Kです。最大クリークは、これ以上頂点を追加できないクリークです。最大クリークの一部ではない各頂点vに対して、クリークに含まれ、かつvに隣接していない別の頂点wが存在しなければならず、v がクリークに追加されるのを妨げます。最大クリークは、可能な限り最大の数の頂点を含むクリークです。クリーク数ω ( G )は、 Gの最大クリークに含まれる頂点の数である。[ 1 ]
密接に関連するいくつかのクリーク発見問題が研究されてきた。[ 14 ]
これらの問題のうち最初の4つはすべて実用的な応用において重要である。クリーク決定問題は実用的な重要性はないが、 NP完全性の理論をクリーク発見問題に適用するためにこのように定式化されている。[ 19 ]
クリーク問題と独立集合問題は相補的である。G のクリークは Gの補グラフの独立集合であり、その逆もまた然りである。[ 20 ]したがって、多くの計算結果はどちらの問題にも同様に適用でき、いくつかの研究論文では 2 つの問題を明確に区別していない。しかし、制限されたグラフの族に適用した場合、2 つの問題は異なる特性を持つ。たとえば、クリーク問題は平面グラフでは多項式時間で解ける可能性があるが[ 21 ] 、独立集合問題は平面グラフでは NP 困難のままである。[ 22 ]
最大クリーク（包含最大とも呼ばれる）は、より大きなクリークに含まれないクリークです。したがって、すべてのクリークは最大クリークに含まれます。[ 23 ]最大クリークは非常に小さい場合があります。グラフには、多数の頂点を持つ非最大クリークと、サイズ 2 の最大クリークが別に存在する場合があります。最大（つまり最大の）クリークは必ずしも最大ですが、その逆は成り立ちません。すべての最大クリークが最大であるグラフの種類がいくつかあります。これらは、すべての最大独立集合が最大であるウェルカバーグラフの補グラフです。 [ 24 ]ただし、最大ではない最大クリークを持つグラフもあります。
単純な貪欲アルゴリズムによって、単一の最大クリークを見つけることができます。任意のクリーク（たとえば、任意の単一の頂点、あるいは空集合）から始めて、グラフの残りの頂点をループして、現在のクリークを一度に 1 つの頂点ずつ拡張します。このループで調べられる各頂点vについて、すでにクリークに含まれているすべての頂点に隣接している場合はv をクリークに追加し、そうでない場合はvを破棄します。このアルゴリズムは線形時間で実行されます。[ 25 ] 最大クリークを見つけることが容易で、そのサイズが小さい可能性があるため、最大または他の大きなクリークを見つけるという、はるかに難しいアルゴリズムの問題により多くの注意が向けられてきました。しかし、並列アルゴリズムに関するいくつかの研究では、最大クリークを見つける問題が研究されています。特に、辞書式順序で最初の最大クリーク（上記のアルゴリズムによって見つかるもの）を見つける問題は、多項式時間関数のクラスに対して完全であることが示されています。この結果は、この問題が並列複雑度クラスNC内で解決できる可能性は低いことを示唆している。[ 26 ]
グラフGにk頂点クリークが含まれているかどうかをテストし、含まれているクリークを総当たりアルゴリズムを使用して見つけることができます。このアルゴリズムは、 k 個の頂点を持つ各部分グラフを調べ、それがクリークを形成しているかどうかを確認します。ビッグ O 表記で表すと、O ( n k k 2 ) の 時間がかかります。これは、チェックする部分グラフが O ( n k ) 個あり、それぞれに G 内に存在するかどうかをチェックする必要がある O ( k 2 ) 個のエッジがあるためです。したがって、 kが固定定数である場合は、この問題は多項式時間で解決できます。ただし、k が固定値ではなく、問題への入力の一部として変化する可能性がある場合は、時間は指数関数的になります。[ 27 ]
クリーク発見問題の最も単純な非自明なケースは、グラフ内の三角形を見つけること、または同等に、グラフが三角形を含まないかどうかを判定することです。m 個のエッジを持つグラフGでは、最大でΘ( m 3/2 )個の三角形が存在する可能性があります (この上限がタイトであることを示すために大きなシータ表記を使用)。この式の最悪のケースは、 G自体がクリークである場合です。したがって、すべての三角形をリストするアルゴリズムは、最悪の場合で少なくともΩ( m 3/2 ) の時間 (大きなオメガ表記を使用) を要し、この時間上限に一致するアルゴリズムが知られています。[ 28 ]例えば、千葉&西関 (1985)は、頂点を次数の高い順から低い順にソートし、ソートされたリストの各頂点vを反復処理して、 vを含み、リスト内の以前の頂点を含まない三角形を探すアルゴリズムを説明しています。そのため、このアルゴリズムはvのすべての隣接点をマークし、 vの隣接点に接続するすべてのエッジを検索して、2 つのマークされた端点を持つすべてのエッジに対して三角形を出力し、次にマークを削除してグラフからvを削除します。著者らが示すように、このアルゴリズムの実行時間は、グラフの樹状度( a ( G )と表記) にエッジの数を掛けたものに比例し、O ( m a ( G ))となります。樹状度は最大でO ( m 1/2 )なので、このアルゴリズムの実行時間はO ( m 3/2 )です。より一般的には、すべてのk頂点クリークは、エッジの数に樹状度の( k − 2乗を掛けたものに比例する時間を要する同様のアルゴリズムによってリスト化できます。平面グラフ（または一般に非自明なマイナークローズドグラフ族のグラフ）のような定常樹状構造のグラフの場合、このアルゴリズムはO ( m ) の時間で実行され、入力サイズに対して線形であるため最適です。[ 18 ]
単一の三角形のみが必要な場合、またはグラフに三角形が含まれていないことを保証したい場合は、より高速なアルゴリズムが可能です。Itai & Rodeh (1978)が指摘しているように、グラフに三角形が含まれるのは、隣接行列と隣接行列の二乗が同じセルに非ゼロのエントリを含む場合のみです。したがって、高速行列乗算技術を適用して、O ( n 2.376 )の時間で三角形を見つけることができます。Alon、Yuster & Zwick (1994)は、高速行列乗算を使用して、三角形を見つけるためのO ( m 3/2 )アルゴリズムをO ( m 1.41 )に改善しました。高速行列乗算に基づくこれらのアルゴリズムは、より大きなkの値に対するkクリークを見つける問題にも拡張されています。[ 29 ]
Moon & Moser (1965)の結果によれば、n頂点のグラフには最大で3 n /3 個の極大クリークが存在する。これらはBron & Kerbosch (1973)の再帰的バックトラッキング手順であるBron–Kerbosch アルゴリズムによって列挙できる。この手順の主要な再帰サブルーチンは 3 つの引数を取る。部分的に構築された (極大ではない) クリーク、クリークに追加できる候補頂点の集合、および追加すべきでない頂点の別の集合 (追加すると既に見つかったクリークにつながるため)。アルゴリズムは候補頂点を 1 つずつ部分クリークに追加し、それぞれに対して再帰呼び出しを行う。これらの頂点をそれぞれ試した後、再度追加すべきでない頂点の集合に移動させる。このアルゴリズムの変種は、最悪の場合の実行時間がO (3 n /3 )であることが示されており、リストアップする必要があるクリークの数と一致します。[ 30 ]したがって、これはすべての最大クリークをリストアップする問題に対する最悪の場合の最適解を提供します。さらに、Bron–Kerbosch アルゴリズムは、実際には他のアルゴリズムよりも高速であることが広く報告されています。[ 31 ]
しかし、クリークの数が最悪の場合よりもかなり少ない場合は、他のアルゴリズムの方が好ましいかもしれません。月山ら（1977）が示したように、生成されたクリークごとに多項式時間でグラフ内のすべての最大クリークをリストアップすることも可能です。彼らのアルゴリズムのように、実行時間が出力サイズに依存するアルゴリズムは、出力依存型アルゴリズムとして知られています。彼らのアルゴリズムは、与えられたグラフGの最大クリークと、 Gから任意の頂点vを削除して形成されるグラフG \ v の最大クリークを関連付ける次の 2 つの観察に基づいています。
これらの観察結果を利用して、彼らは、任意の頂点 v を選択し、 G \ v の各最大クリーク K に対して、 Kと、vをKに追加してvの非隣接頂点を削除して形成されるクリークの両方を出力する再帰アルゴリズムによって、 Gのすべての最大クリークを生成できます。ただし、Gのクリークの中には、このようにして複数の親クリークから生成されるものもあるため、G \ vの親がすべての可能な親クリークの中で辞書式最大である場合にのみGのクリークを出力することで重複を排除します。この原理に基づいて、彼らは、G のすべての最大クリークは、クリークごとに O ( mn ) の時間で生成できることを示しました。ここで、mはGのエッジの数、nは頂点の数です。千葉&西関 (1985) はこれをクリークごとにO ( ma )に改善しました。ここで、 aは与えられたグラフの樹状度です。Makino & Uno (2004)は、高速行列乗算に基づく出力依存型の代替アルゴリズムを提案している。Johnson & Yannakakis (1988)は、最大クリークを辞書式順序で、クリークごとに多項式遅延で列挙することも可能であることを示している。ただし、このアルゴリズムの効率性には順序の選択が重要であり、この順序の逆の場合、P = NPでない限り、多項式遅延アルゴリズムは存在しない。
この結果に基づいて、クリークの数が多項式的に制限されているグラフの族については、すべての最大クリークを多項式時間で列挙することが可能です。これらの族には、弦グラフ、完全グラフ、三角形のないグラフ、区間グラフ、有界ボックス性を持つグラフ、および平面グラフが含まれます。[ 32 ]特に、平面グラフには、最大で定数サイズのO ( n )個のクリークがあり、線形時間で列挙できます。これは、疎（エッジの数が頂点の数の定数倍以下）であり、かつ部分グラフを取る操作に関して閉じているグラフの族についても同様です。 [ 18 ] [ 33 ]
任意のn頂点グラフの最大クリーク、またはクリーク番号は、上記のアルゴリズムのいずれかを使用してグラフ内のすべての最大クリークをリストし、最大のクリークを返すことで、 O (3 n /3 ) = O (1.4422 n )の時間で見つけることができます。ただし、このクリーク問題の変種では、より良い最悪時間境界が可能です。Tarjan と Trojanowski (1977) のアルゴリズムは、この問題をO (2 n /3 ) = O (1.2599 n ) の時間で解決します。これはBron – Kerboschアルゴリズムと同様の再帰バックトラッキング方式ですが、呼び出し内で見つかったクリークが最適ではないことが示せる場合は、一部の再帰呼び出しを省略できます。Jian (1986)は時間をO (2 0.304 n ) = O (1.2346 n )に改善し、Robson (1986)はより多くのメモリ使用量を犠牲にして、時間をO (2 0.276 n ) = O (1.2108 n )に改善しました。Robson のアルゴリズムは、同様のバックトラッキング スキーム (より複雑なケース分析付き) と、補グラフのすべての小さな連結部分グラフに対して最適解を事前に計算する動的計画法の手法を組み合わせています。これらの部分解は、バックトラッキングの再帰を短縮するために使用されます。現在知られている最速のアルゴリズムは、Robson (2001)によるこの方法の改良版で、実行時間はO (2 0.249 n ) = O (1.1888 n )です。[ 34 ]
最大クリーク問題を最悪実行時間の保証なしに解くためのヒューリスティックアルゴリズムについても、分岐限定法[ 35 ] 、局所探索法[ 36 ] 、貪欲アルゴリズム[ 37 ] 、制約プログラミング[ 38 ]などの手法に基づいて、広範な研究が行われてきました。クリークを見つけるために提案された非標準的な計算手法には、DNA コンピューティング[ 39 ]や断熱量子計算[ 40 ]などがあります。最大クリーク問題は、1992～1993 年にDIMACSが主催した実装チャレンジの対象となり[ 41 ]、そのチャレンジのベンチマークとして使用されたグラフのコレクションが公開されています[ 42 ] 。
平面グラフやその他の疎グラフの族については既に述べたとおり、線形時間で列挙できる、サイズが制限された線形数の極大クリークが存在する。[ 18 ]特に、平面グラフの場合、クラトフスキーの定理により、どのクリークも最大で4つの頂点しか持たない。[ 21 ]
完全グラフは、クリーク数が彩色数に等しく、この等号が誘導部分グラフのそれぞれでも成り立つという性質によって定義されます。完全グラフの場合、半正定値計画法に基づくアルゴリズムを使用して、多項式時間で最大クリークを見つけることができます。[ 43 ] ただし、この方法は複雑で非組み合わせ的であるため、完全グラフの多くのサブクラスに対して、専用のクリーク探索アルゴリズムが開発されています。[ 44 ]二部グラフの補グラフでは、ケーニッヒの定理により、マッチングの手法を使用して最大クリーク問題を解くことができます。完全グラフの別のクラスである順列グラフでは、最大クリークはグラフを定義する順列の最長減少部分列であり、最長減少部分列問題に対する既知のアルゴリズムを使用して見つけることができます。逆に、最長減少部分列問題のすべてのインスタンスは、順列グラフで最大クリークを見つける問題として等価に記述できます。[ 45 ]さらに、Pnueli & Lempel (1972)は、順列グラフを特殊なケースとして含む、より広いクラスの完全グラフである比較グラフで最大クリークを見つけるための別の二次時間アルゴリズムを提供しています。[ 46 ]弦グラフでは、頂点を消去順序でリストし、この順序で各頂点のクリーク近傍をチェックすることで、最大クリークを見つけることができます。[ 47 ]
場合によっては、これらのアルゴリズムは、他の非完全なグラフのクラスにも拡張できます。たとえば、円グラフでは、各頂点の近傍は順列グラフであるため、円グラフの最大クリークは、各近傍に順列グラフアルゴリズムを適用することによって見つけることができます。[ 48 ]同様に、単位円盤グラフ（既知の幾何学的表現を持つ）では、2部グラフの補グラフのアルゴリズムを頂点のペアの共有近傍に適用することに基づく、最大クリークの多項式時間アルゴリズムがあります。[ 49 ]
Erdős–Rényi モデル(各エッジが他のエッジとは独立に確率1/2で出現する)から抽出されたランダム グラフで最大クリークを見つけるアルゴリズムの問題は、Karp (1976)によって提案されました。ランダム グラフの最大クリークは高い確率で対数サイズであるため、総当たり探索で期待時間2 O (log 2 n )で見つけることができます。これは準多項式時間制限です。[ 50 ]このようなグラフのクリーク数は通常2 log 2 nに非常に近いですが、単純な貪欲アルゴリズムやより洗練されたランダム化近似手法では、半分のサイズであるlog 2 nのクリークしか見つかりません。このようなグラフの最大クリークの数は、高い確率でlog 2 nの指数関数的であるため、すべての最大クリークをリストするメソッドが多項式時間で実行されなくなります。[ 51 ]この問題の難しさから、いくつかの著者は、大きなクリークを追加することによって拡張されたランダムグラフ上のクリーク問題である、植え付けられたクリーク問題を研究してきました。 [ 52 ]スペクトル法[ 53 ]および半正定値計画法[ 54 ]はサイズΩ( √ n )の隠れたクリークを検出できますが、サイズo ( √ n ) (小文字の o 表記で表現)のクリークを検出する多項式時間アルゴリズムは現在知られていません。[ 55 ]
複数の著者が、最大ではないものの、多項式時間で見つけられる限り最大に近いサイズのクリークまたは独立集合を見つけようとする近似アルゴリズムを検討してきた。この研究の多くは、疎グラフの独立集合に焦点を当ててきたが、これは相補クリーク問題には意味をなさないケースである。しかし、このような疎性の仮定を使用しない近似アルゴリズムに関する研究も行われている。[ 56 ]
Feige (2004) は、任意の定数kに対してクリーク数がΩ( n / log k n )である任意のグラフにおいて、サイズΩ((log n / log log n ) 2 )のクリークを見つける多項式時間アルゴリズムを記述している。与えられた入力グラフのクリーク数がn /log nからn /log 3 nの間にある場合にこのアルゴリズムを使用し、クリーク数が大きいグラフに対してはBoppana & Halldórsson (1992)の別のアルゴリズムに切り替え、両方のアルゴリズムが何も見つけられなかった場合は 2 頂点のクリークを選択することで、Feige は、最大値のO( n (log log n ) 2 /log 3 n )の係数以内の頂点数を持つクリークを見つける近似アルゴリズムを提供している。このアルゴリズムの近似比は弱いものの、現在までに知られている最良のものである。[ 57 ]以下に述べる近似の難しさに関する結果は、近似比が線形より著しく小さい近似アルゴリズムは存在しないことを示唆している。
クリーク決定問題はNP完全問題です。これは、リチャード・カープが1972年の論文「組み合わせ問題間の還元可能性」でNP完全問題として示した21個の問題の1つでした。[ 59 ] この問題は、スティーブン・クックがNP完全問題の理論を紹介した論文でも言及されています。[ 60 ]決定問題の難しさから、最大クリークを見つける問題もNP困難です。これを解くことができれば、最大クリークのサイズを決定問題への入力として与えられたサイズパラメータと比較することで、決定問題も解くことができます。
カープのNP完全性の証明は、ブール充足可能性問題からの多対一還元である。これは、連言標準形（CNF）のブール式を最大クリーク問題の同等のインスタンスに変換する方法を記述している。[ 61 ]一方、充足可能性はクック・レヴィンの定理でNP完全であることが証明されている。カープは、与えられたCNF式から、vが変数またはその否定であり、cがvを含む式の節であるすべてのペア（v、c）に対して頂点を持つグラフを形成する。これらの頂点のうち2つは、異なる節に対する互換性のある変数割り当てを表す場合にエッジで接続されている。つまり、 c ≠ dであり、uとvが互いの否定でない場合、 （v、c）から（u、d）へのエッジが存在する。 CNF式における節の数をkとすると、このグラフのk頂点クリークは、式を満たすためにいくつかの変数に真理値を割り当てる一貫した方法を表す。したがって、式が充足可能であるのは、 k頂点クリークが存在する場合のみである。[ 59 ]
NP完全問題の中には（平面グラフにおける巡回セールスマン問題など）、入力サイズパラメータnの準線形関数で指数関数的な時間で解けるものがあり、総当たり探索よりもかなり高速です。[ 62 ]しかし、任意のグラフにおけるクリーク問題に対して、このような準指数関数的な時間制限が可能である可能性は低いでしょう。なぜなら、それは他の多くの標準的なNP完全問題に対しても同様に準指数関数的な制限を意味することになるからです。[ 63 ]
クリーク問題の計算上の困難さから、回路複雑性のいくつかの下限を証明するためにクリーク問題が利用されてきた。与えられたサイズのクリークの存在は単調グラフ特性であり、与えられたグラフにクリークが存在する場合、任意のスーパーグラフにもクリークが存在することを意味する。この特性は単調であるため、与えられた固定クリークサイズに対してクリーク決定問題を解くために、 ANDゲートとORゲートのみを使用する単調回路が存在する必要がある。しかし、これらの回路のサイズは、頂点の数とクリークサイズの超多項式関数であり、頂点数の立方根に対して指数関数的であることが証明できる。[ 64 ]少数のNOTゲートが許容される場合でも、複雑性は超多項式のままである。[ 65 ]さらに、ファンインが制限されたゲートを使用するクリーク問題の単調回路の深さは、少なくともクリークサイズの多項式でなければならない。[ 66 ]
グラフの特性を決定する（決定論的）決定木の複雑さは、グラフが特定の特性を持つかどうかを判断するために最悪の場合に回答しなければならない「頂点uと頂点vの間にエッジはありますか？」という形式の質問の数です。つまり、これは問題に対するブール決定木の最小の高さです。質問できる可能性のある質問はn ( n − 1)/2 個あります。したがって、任意のグラフ特性は最大でn ( n − 1)/2 個の質問で決定できます。特性のランダムおよび量子決定木の複雑さを定義することもできます。これは、ランダム化または量子アルゴリズムが、与えられたグラフがその特性を持つかどうかを正しく判断するために回答する必要がある質問の期待値（最悪の場合の入力に対して）です。[ 67 ]
クリークを含む性質は単調であるため、任意の非自明な単調グラフ性質を決定する決定論的決定木の複雑さが正確にn ( n − 1)/2であると述べるAanderaa–Karp–Rosenberg 予想によってカバーされます。任意の単調グラフ性質については、この予想は未証明のままです。しかし、決定論的決定木の場合、2 ≤ k ≤ nの範囲の任意のkに対して、 kクリークを含む性質の決定木の複雑さが正確にn ( n − 1)/2であることがBollobás (1976)によって示されました。決定論的決定木は、クリークを検出するために指数関数的なサイズ、または制限されたサイズのクリークを検出するために大きな多項式的なサイズも必要とします。[ 68 ]
Aanderaa–Karp–Rosenberg予想では、非自明な単調関数のランダム化決定木の複雑度はΘ( n 2 )であるとも述べられています。この予想は未だ証明されていませんが、 2 ≤ k ≤ nのkクリークを含む性質については解決されています。この性質はランダム化決定木の複雑度がΘ( n 2 )であることが知られています。[ 69 ]量子決定木の場合、既知の最良の下限はΩ( n )ですが、 k ≥ 3の場合のマッチングアルゴリズムは知られていません。[ 70 ]
パラメータ化複雑性とは、小さな整数パラメータkが自然に備わっており、 k が増加するにつれて問題が難しくなる問題（グラフにおけるkクリークの探索など）の複雑性理論の研究である。問題は、入力サイズnと関数fに対して、アルゴリズムがf ( k ) n O (1)の時間で実行されるようなアルゴリズムが存在する場合、固定パラメータ扱い可能であると言われる。つまり、任意の固定kの値に対して多項式時間で解くことができ、さらに多項式の指数がkに依存しない場合、固定パラメータ扱い可能である。[ 71 ]
k頂点クリークを見つけるための総当たり探索アルゴリズムの実行時間はO( n k k 2 )です。 nの指数はkに依存するため、このアルゴリズムは固定パラメータ扱い可能ではありません。高速行列乗算によって改善できますが、実行時間は依然としてkに対して線形な指数を持ちます。したがって、クリーク問題に対する既知のアルゴリズムの実行時間は任意の固定kに対して多項式ですが、これらのアルゴリズムは固定パラメータ扱い可能には十分ではありません。DowneyとFellows (1995) は、固定パラメータ扱い可能なアルゴリズムを持たないと推測した、パラメータ化された問題の階層 W 階層を定義しました。彼らは、独立集合 (または同等にクリーク) がこの階層の最初のレベルW[1]に対して困難であることを証明しました。したがって、彼らの推測によれば、クリークには固定パラメータ扱い可能なアルゴリズムはありません。さらに、この結果は他の多くの問題のW[1]困難性の証明の基礎となり、したがってパラメータ化された複雑性に対するクック・レヴィン定理の類似物として機能する。[ 72 ]
Chen et al. (2006)は、指数時間仮説が成り立たない限り、k頂点クリークを見つけるのに時間n o ( k )を要しないことを示した。これもまた、固定パラメータの扱いやすいアルゴリズムは不可能であるという証拠となる。[ 73 ]
最大クリークを列挙する問題や最大クリークを見つける問題は、パラメータkでは固定パラメータ扱い可能とは考えにくいが、インスタンス複雑性の他のパラメータでは固定パラメータ扱い可能となる可能性がある。例えば、入力グラフの縮退度でパラメータ化した場合、両方の問題が固定パラメータ扱い可能であることが知られている。[ 33 ]
クリーク問題の近似が難しいことを示唆する弱い結果は、長い間知られていました。Garey & Johnson (1978)は、クリーク数が小さな整数値を取り、計算が NP 困難であるため、 P = NP でない限り、完全な多項式時間近似スキームは存在しないことを指摘しました。近似が正確すぎる場合は、その値を整数に丸めることで正確なクリーク数が得られます。しかし、1990 年代初頭に、数人の著者が最大クリークの近似と確率的に検証可能な証明との関連性を指摘し始めるまで、それ以上のことはほとんど知られていませんでした。彼らはこれらの関連性を使用して、最大クリーク問題の近似結果の困難性を証明しました。 [ 74 ] これらの結果に多くの改良が加えられた結果、現在では、すべての実数ε > 0に対して、 P = NPでない限り、最大クリークをO ( n 1 − ε )より優れた係数で近似する多項式時間アルゴリズムは存在しないことが知られています。[ 75 ]
これらの近似不可能性結果の基本的な考え方は、ブール充足可能性問題のようなNP完全問題に対する確率的に検証可能な証明システムを表すグラフを構築することです。確率的に検証可能な証明システムでは、証明はビット列として表現されます。充足可能性問題のインスタンスは、充足可能である場合に限り、有効な証明を持つ必要があります。証明は、充足可能性問題への入力に対して多項式時間計算を行った後、証明文字列のランダムに選択された少数の位置を調べるアルゴリズムによってチェックされます。そのビットのサンプルで見つかった値に応じて、チェッカーは残りのビットを見ることなく、証明を受け入れるか拒否するかを決定します。偽陰性は許されません。有効な証明は常に受け入れられなければなりません。ただし、無効な証明が誤って受け入れられる場合もあります。無効な証明ごとに、チェッカーがそれを受け入れる確率は低くなければなりません。[ 76 ]
この種の確率的に検証可能な証明システムをクリーク問題に変換するには、証明チェッカーの可能な受理実行ごとに頂点を持つグラフを作成します。つまり、頂点は、検査する位置の集合の可能なランダムな選択の 1 つと、チェッカーが証明を受理する原因となる位置のビット値によって定義されます。これは、検査した各位置に 0 または 1 があり、残りの各位置にワイルドカード文字がある部分ワードで表すことができます。このグラフでは、対応する 2 つの受理実行が、両方とも検査するすべての位置で同じビット値を見る場合に、2 つの頂点は隣接しています。各 (有効なまたは無効な) 証明文字列は、その証明文字列を見る受理実行の集合であるクリークに対応し、すべての最大クリークはこのようにして発生します。これらのクリークの 1 つは、多くの証明チェッカーが受理する証明文字列に対応する場合に限り、大きくなります。元の充足可能性インスタンスが充足可能であれば、有効な証明文字列、つまりチェッカーのすべての実行で受け入れられる証明文字列が存在し、この文字列はグラフ内の大きなクリークに対応します。しかし、元のインスタンスが充足不可能であれば、すべての証明文字列は無効であり、各証明文字列は誤って受け入れるチェッカーの実行が少数しかなく、すべてのクリークは小さくなります。したがって、大きなクリークを持つグラフとすべてのクリークが小さいグラフを多項式時間で区別できる場合、またはクリーク問題を正確に近似できる場合、充足可能性インスタンスから生成されたグラフにこの近似を適用することで、充足可能なインスタンスと充足不可能なインスタンスを区別することができます。ただし、これは P = NP でない限り不可能です。[ 76 ]
{{citation}}: CS1 maint: postscript (リンク)。