最大クリーク問題の現在
Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースでがはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。
大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあった
www.slideshare.net
最大クリークの計算量とか(続き) - 高温処理済みコースケでも書いてたのとほぼ同じ形になっていったため、この畳み込みの式をみて、方向性はわるくないことがわかった。
辺の重みは自分で作って、それを修正する形で最大クリークサイズをもとめればいいことに気づいた。
辺の重みはにして、の関係を利用する。
最初は二分探索してて、Dinkelbachにしたいんだけどって感じで。。。でも、g(t)を支える直線に沿って進むのがイメージしにくかったのと、比じゃないしとおもっていて困っていた。
結果、まあ納得いくソースになった。特に超denseのときにもつらくないのがよい。
判定ならn = 200, m = 4565, k = 14を探すのに2.74秒、プログラミングコンテストの問題とかでも行けそう。
$ time bin/max_clique -k 14 < fixtures/clique/N200M4565C14.txt 14 9 11 13 47 52 57 61 90 126 150 158 170 180 192 real 0m2.749s user 0m0.030s sys 0m0.015s
最大クリーク問題で面白いなとおもったこと
いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。
ある無向グラフGについてを最大クリークサイズを返す関数とする。
f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフをとすると
g(m) : グラフが非連結で、連結グラフn個に分かれているとする、その各グラフをとすると
h(k) : 頂点をうまく分割するとサイズkのクリーク(はサイズkのクリークの集合)と、その全点から接続している頂点とそれ以外。
となるのが極大クリーク。
上記を踏まえ、判定式をつくる
f(w)のうち、補グラフで孤立点(元のグラフでは自身を除く全点と接続)となっているものを取り出す処理をp(n)とする。で処理できる。
h(k)はk=2に固定したとp(n)と畳み込み使って、下記のように表すことができる。
g(m)についてはが、Eを順次探索するのでその時に一緒にやってしまえる(実装では辺に対してBFS, クリークに対してDFSとなっている)のであまり考えなくてよい。f(w)の孤立点以外については実装は簡単(UnionFind)でできるけど、そのケースにどれくらい当てはまるかが微妙なのと補グラフの辺はもっていないので掛けてつくるかが微妙、濃度に合わせてやるのが良さそうという感じをもっている。
とりあえずABC002 派閥で試してhttp://abc002.contest.atcoder.jp/submissions/1271432はRubyでは最速になってた。C++と比べるとおそいけどスピンアップの時間考えるとかなり速いと思う。
Cのコード見てると隣接行列使って解いてるっぽいコードがあった。すげぇ早い
メモ: 下記の論文によると補グラフのBFSやDFSをでできるらしい。なら、やればよいかという気がしている。
補グラフでの最小頂点被覆ってなんだろう?
補グラフでの最小頂点被覆ってなんだろう?って考えてて、最大クリークの頂点以外の頂点集合って意味しかないのかな
最大クリークの途中で補グラフが出てくる話
kousuke.hatenablog.com
前回、ワーストケースでになると書いた。
FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか?
簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。
最大クリーク判定の式をおさらいする。は自身を除く全点に接続している頂点。
3番目をA式、4番目をB式と呼ぶ。
A式では全点につながった辺はまとめて処理でき、ここは分岐する必要がない。また、この処理で辺は一気に減っているけど、補グラフの辺は実は減ってない。このことからも極大クリークを示すのに適当そうな感じがする。またA式の処理により、B式を処理するときには、すべての頂点は必ずどこかの頂点とつながっていない。そのため、補グラフに辺がある。ということでここから補グラフで展開していく。
補グラフの辺の数をwとする。となる。
D式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を1本以上含んでいるので、D式処理後、必ず補グラフの辺は2つ以上減る。
計算量はざっとが想定される。
とはいえワーストケースがk/2で収まるので、準指数でも大きそう。
なのでP=NPか、P≠NPでも、比較的小さいところでより小さくなる関数じゃないかとおもっている。もしかすると虚数がでてきて、k/2とどちらか速い方の可能性もある。
最小頂点被覆の計算量でが示せればよいとしてCを求めるやつだと、そのままwに置き換えるとになるんでか、1ならP=NPかもしれない。
最大クリークの計算量とか(続き)
kousuke.hatenablog.com
大事なことに気が付いたので、前回の修正。
単純な無向グラフに対し、をサイズkのクリークが含まれるかどうかを判定する関数とする。
グラフGに自身を除く全頂点に接続する頂点がある場合、それらは必ず最大クリークに含まれる。そのような頂点集合をとすると、下記が成り立つ。
の場合を考える。
頂点vに隣接している頂点の集合をとし、に対し、とする。ならば、eを含むサイズ3のクリークが存在し、誘導部分グラフの中にeを含むクリークが全て含まれる。よって次式が成り立つ。
の頂点はすべてeに接続しているので、にサイズk-2のクリークがあればよいので、さらに次式のように変形できる。
終了条件も含め、下記のようになる。
またにサイズkのクリークが含まれない場合、Gからeを取り除いても最大クリークには影響しない。
は辺を評価していると見ることができる。とする。
であれば、即座にその辺を除去する前処理を行う。この前処理の結果、少なくともサイズ3のクリークをk-2個以上含む辺のみが残り、各頂点の次数はk-1以上になる。
また次数がk-1未満になる頂点はその時点で除去できる。そのため、前処理後のグラフに対し、すべての辺を評価しなくともよい。
評価する辺の集合が最小のものをとし、を取り除いたグラフをとする。
下式よりおよその辺を評価すれば良いことがわかる。
最悪でも深さk/2の有界探索木だとおもうのでの目がある。
結局FPTなんだけど、そのパラメーターは極大クリークの数に依存する。上記のワーストケースは常にの場合で、どんなにクリークサイズが大きくても、完全グラフ-数辺みたいのだとあっという間に終わる。
前回は全点に接続する頂点を書いてなくて、終了条件に完全グラフって書いてたけど、これでぐっと見通しがよくなった。
次は補グラフでの最大独立集合を考えることにする。
を使った前処理の実装例
#!/usr/bin/env ruby require 'optparse' def shave_by_clique(g, eset, c) eset.reject {|u,v| (g[v] & g[u]).size < c } end def build_graph(g,vset,eset) vset.each {|v| g[v] = [] } eset.each {|u,v| g[v] << u; g[u] << v } end c = 3 opt = OptionParser.new opt.on('-c C', 'lower number bounds of 3-cliques.'){|v| c = v.to_i } opt.parse!(ARGV) n, m = gets.split.map(&:to_i) V = n.times.to_a E = m.times.map { gets.split.map(&:to_i) } G = {} eset = E build_graph(G,V,E) loop do shaved = shave_by_clique(G, eset, c - 2) if eset.size == shaved.size break end G.clear build_graph(G, V, shaved) eset = shaved end vset = eset.flatten.uniq.sort index = {} vset.each_with_index{|v,i| index[v] = i } puts "#{vset.size} #{eset.size}" puts eset.map{|e| e.map{|v| index[v] }}.map{|e| e.join(' ')} puts "# #{vset.join(' ')}"
グラフと補グラフの関係
n頂点の完全グラフを、独立グラフ(頂点のみで辺がないグラフ)をとする。
n頂点のグラフがある。
このときからへひとつづつ辺を消していく順序集合のうち、を含む順序の集合を定めることができる。
このときのどの順序を通ってもの補グラフはない。
そのためのような構造を考えることができる。
の辺の数はでと位相がずれていて、でに戻るので、上の構造はと同相と考えることができそう。
同様にも位相が離れているとみることができそう。
また最大クリーク問題を考えると頂点がなくなる方向への順序集合(こちらは頂点集合)もある。
最大クリーク問題の解はとの方向が一致することができる最大のnとみることができる。
なんとなくグラフを複素数の多項式として表せるんじゃないかとおもっていて、上の式を頂点方向と辺方向で全微分とかすると、その極大値が最大クリークにならないだろうかとかおもっていたりする。
またイメージとしてはに対し、への自己ループの輪()とを結ぶ輪が通っており、が縮もうとするときの緊張関係のように考えることができそう。
追記
ないとおもったけど、同型ならあるんだよね。とか考えると同型ならのなかにあるわ。
P=NPだと夢がある。
kousuke.hatenablog.com
頂点に関しては極大グラフが1つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。
あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。
これは一緒に補グラフの最大独立問題をやってるに等しい。
少なくとも、NP完全問題が難しいのは、頂点に関するものと辺に関するものを両方一緒にやるからというのが現在の認識。
全部辺の問題に還元しながらやっていくのがたぶんよい。
追記
下記の資料をみていて、葉最大全域木でなんかインスピレーション湧いた。
補グラフの辺はなんで、これを0に近づけていくと良いし、葉最大で葉を指定するのは難しいけど、次数使って辺をうまく重みづけできそうだし、その最小全域木に沿って処理できれば、Dinkelbach algorithmで結構高速にできそう。
追記2
最大クリーク問題である条件下で、多項式時間で計算量一気に短縮できる処理があって、それを常に続けられると多項式時間になるのになぁとおもっている。