読者です 読者をやめる 読者になる 読者になる

最大クリーク問題

まだうまく証明できていないかもしれないけど、これで解けてると思う解けていないです。

別の実装を考えたのでコードを消しました。

kousuke.hatenablog.com


belongs_max_cliqueではある頂点を含む極大クリークのサイズを返していて、それを全点に対して行いその最大のものを出力している。

belongs_max_cliqueは任意の1頂点(v)とそれに隣接する頂点集合をUとすると、誘導部分グラフG[U]に対し、その次数をまず計算する。 Uの次数の少ないものから、順に切断していくと最終的に他の全ての点と同じ次数になるので、その時残っているグラフがvを含む最大クリークとなる。 クリークのサイズは次数 + 1すればよい。

(証明)

  • 最大クリークはそのグラフの頂点のどれかを含んでいる(自明)
  • ある頂点を選んでその頂点を含む極大クリークがわかれば、それを全点でおこなうことで最大クリークがわかる。(問題ないとおもう)
  • G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vを含むクリークはすべて含まれる。(多分、自明)
  • G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vの次数は必ず他の頂点の次数以上である。(Uの頂点数がnならG[U]の頂点の次数はn-1より大きくなることはなく、vの次数はn-1)
  • G[U]が完全グラフ(Kn)のとき、その全ての頂点の次数はn-1となり、頂点数はnとなり、停止条件となる。(n-正則グラフの場合があり、判定できてない)
  • G[U]からvの次数未満の最小の次数をもつ頂点を1点切断した頂点集合をU'とするとG[U']も必ずvを含む極大クリークが含まれる。(問題あり)
  • U'をUとして5に戻っても矛盾はない。(問題ないとおもう)

以上より、このアルゴリズム停止条件をもち、有限時間内に停止する。 またその時、このグラフに含まれる極大クリークのうち、最大のサイズを示す。

計算量はちょっと自信がないけど、頂点数をv , 次数の平均をdとすると O(v * d^2) じゃないかとおもう。 次数の平均はE / VなのでO(E^2 / V)かな。

以下、コーナーケースとして指摘されそうな例

  • G[U]が2つの完全グラフ(Kn,Km)を含み、その節点がvのとき、vは次数n+m - 2をもち、vを除くKn,Kmに含まれる点はそれぞれn-1,m-1の次数をもつ。
    • n < mのとき、Knの点から順に切断され、最終的にKmだけ残りすべての頂点がm-1の次数をもつ。
    • n = mのときはvをのぞく全ての点がn-1の次数を持ち、そのうち1点を切断することで、n < mと同じ状況になる。
  • G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点を結ぶ接続がある場合も、上記のケースでの切断する順序に変化があるだけで、同様に最大クリークを返す。
  • G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点にすべて接続がある場合、それは完全グラフKn+m-1であり、同様に最大クリークを返す。

TODO: 課題

  • 全ての次数が同じだけど、片側に完全Kn,もう片側にn-1正則グラフがある場合

この状況を把握するのはおそらく無理、右側と左側にリンクがある場合もあるので、フローとかで優先順位を確定できない限り難しい。もしかすると現在の実装でも、それなりに正しいものを出すかもしれないけど、コーナーケースのデータは否定できない。

- 案1. V.each前にsortするかbelongs_max_clique内のsortでabsを使用しているが、これを変えて、全体の順序のなかで順序付けして、整合性が取れるようにする。もしくは現在の状況で整合性がとれていることを示す必要がある。

- 案2. 完全グラフかどうかはキーの数 = 次数 + 1かどうかで判定できるので、そうでない場合はスキップする。この場合も全体のなかで整合性が取れている必要がある。もしくは優先順位を変えて再度実施する。

とりあえず完全グラフかどうか頂点数と次数で判定して、正則グラフの場合は-1を返すようにしてみた。ただ全体の整合性がとれるのかというと違う。もちろん右側と左側の別の頂点でbelong_max_cliqueは呼ばれるけど、全ての頂点がn-正則グラフと隣接しているというような状況はある。