基本的には前書いた内容。kousuke.hatenablog.com1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で二分探索する。contain_clique?で求めるクリークのサイズcを指定する。critical_subgraph_by_degreeで頂点の次数が全てc-1以上となるような部分グラフを探す。super_clique_exist?で指定したクリーク(最初は辺e)を含む、サイズcの拡大クリークを再帰的に探していく。指定したクリークが求めるサイズのクリークならtrueを返して終了。+1サイズの拡大クリークがなければ、それは極大クリークで求めるサイズのクリークでないのでfalseを返して終了。現在のクリークサイズが、求めるクリークサイズc未満なら、その時点でサイズcのクリークには含まれないのでfalseを返して終了。+1サイズの拡大クリークについて3を再帰的に行って、サイズcのクリークを探す。辺eを削除する説明サイズcのクリークは必ず全頂点がc-1の次数をもっているので、次数c-1未満の点を削除するというのを繰り返してもそのクリークはなくならない。このグラフをG'とする。次にG'に含まれる辺eに対し、eを含むクリーク全体を評価していく。のどの頂点をeに加えてもサイズ3のクリークになり、これはサイズ3以上のクリークでも同様。基本的には計算量は極大クリークの数とその重複度合による。ある辺eがサイズc未満の極大クリーク1つだけに含まれる場合、super_clique_exist?内で、3-2のケースにあたり再帰なしに枝刈される。同様に複数の極大クリークに含まれていて、再帰が深くなっていっても、極大クリーク1つに確定できるようになった時点でサイズc未満なら枝刈できる。含まれない頂点を選択した時点で枝刈出来る。3つ以上の極大クリークに含まれる場合も同様。最終的にサイズcのクリークがなければ、辺eを消し*1、次の辺e'を含む評価に進む。辺eを含んでいたクリークはだんだん細かく分断されていくけど、辺eを含んでいたクリーク全体は評価が終わっているので、他の辺e'を含むクリーク全体を評価する際に求めるサイズのクリークを小さくしたりはしない。辺eを含んでいた極大クリークは小さく分断されていくことで他の極大グラフに含有されば、別の辺での計算量は次第に減っていくことになる。最悪ケースでは全部のクリークを探すとかになるかもしれないけど、まあまあ速いとおもう。二分探索をやるなかで、枝刈りしたところを何度も確認することになるので、枝刈時点のクリークと可能性のある最大サイズをキャッシュしておいて探すクリークのサイズが変更になったらそこから継続するとかすれば、もうすこし早くなりそう。(追記)各頂点毎にd(v)-c+2個の辺を評価して目的サイズのクリークがなければ、次数はc-1未満になり、その頂点は削除できるので上手く実装できれば少し速くなりそう。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。