続々々 最大クリーク問題(2)
すこしコードを変更している。興味ある人はpaiza.ioで動かしてみてほしい。
https://paiza.io/projects/14TYw6RR2KIPBLRjSNCPrg
V=1000、E=9988、20彩色可能、最大次数 69、次数の分布具合は下記のグラフを参考。
最大クリークは8。列挙しているわけではないので、複数ある可能性もある。
続々々 最大クリーク問題
基本的には前書いた内容。
kousuke.hatenablog.com
1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。
動作
0. 頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で二分探索する。
1. contain_clique?で求めるクリークのサイズcを指定する。
2. critical_subgraph_by_degreeで頂点の次数が全てc-1以上となるような部分グラフを探す。なければこの時点で終わり
3. super_clique_exist?で指定したクリーク(最初は辺e)を含む、サイズcの拡大クリークを再帰的に探していく。
3-1. 指定したクリークが求めるサイズのクリークならtrueを返して終了。
3-2. +1サイズの拡大クリークがなければ、それは極大クリークで求めるサイズのクリークでないのでfalseを返して終了。
3-3. +1サイズの拡大クリークの数 + 現在のクリークサイズが、求めるクリークサイズc未満なら、その時点でサイズcのクリークには含まれないのでfalseを返して終了。
3-4. +1サイズの拡大クリークについて3を再帰的に行って、サイズcのクリークを探す。
4. 辺eを削除する
説明
サイズcのクリークは必ず全頂点がc-1の次数をもっているので、次数c-1未満の点を削除するというのを繰り返してもそのクリークはなくならない。このグラフをG'とする。
次にG'に含まれる辺eに対し、eを含むクリーク全体を評価していく。
e = {u,v}とし、u,vが接続している頂点の集合とする。
のどの頂点をeに加えてもサイズ3のクリークになり、これはサイズ3以上のクリークでも同様。
また辺eを含むクリーク全体はのべき集合の中にある。
基本的には計算量は極大クリークの数とその重複度合による。
ある辺eがサイズc未満の極大クリーク1つだけに含まれる場合、super_clique_exist?内で、3-2のケースにあたり再帰なしに枝刈される。同様に複数の極大クリークに含まれていて、再帰が深くなっていっても、極大クリーク1つに確定できるようになった時点でサイズc未満なら枝刈できる。
他にもの3つのクリークに含まれる場合(すべてサイズはc未満)でもならば、に含まれない頂点を選択した時点で枝刈出来る。3つ以上の極大クリークに含まれる場合も同様。
最終的にサイズcのクリークがなければ、辺eを消し*1、次の辺e'を含む評価に進む。
辺eを含んでいたクリークはだんだん細かく分断されていくけど、辺eを含んでいたクリーク全体は評価が終わっているので、他の辺e'を含むクリーク全体を評価する際に求めるサイズのクリークを小さくしたりはしない。また元々辺eを含んでいた極大クリークは小さく分断されていくことで他の極大グラフに含有されば、別の辺での計算量は次第に減っていくことになる。
最悪ケースでは全部のクリークを探すとかになるかもしれないけど、まあまあ速いとおもう。
もうすこし改良できる点。
二分探索をやるなかで、枝刈りしたところを何度も確認することになるので、枝刈時点のクリークと可能性のある最大サイズをキャッシュしておいて探すクリークのサイズが変更になったらそこから継続するとかすれば、もうすこし早くなりそう。
(追記)
各頂点毎にd(v)-c+2個の辺を評価して目的サイズのクリークがなければ、次数はc-1未満になり、その頂点は削除できるので上手く実装できれば少し速くなりそう。
コード
class Graph def initialize(vset, eset) @v = vset.to_a @e = eset.to_a @g = nil recreate_graph! end def recreate_graph! @g = {} @v.each{|v| @g[v] = []} @e.each{|u,v| @g[u] << v; @g[v] << u } nil end def _super_clique_exist?(clq, limit = clq.size + 1, cache = {}, &found) clqs = clq.sort.join(' ') if cache[clqs] return false else cache[clqs] = true end if clq.size == limit found && found.call(clq) return clq end vset = clq.inject(verteces) {|s, v| s & self[v] } if vset.size >= limit - clq.size vset.any? {|v| _super_clique_exist?(clq + [v], limit, cache, &found) } else false end end protected :_super_clique_exist? def contain_clique?(c, &found) g = critical_subgraph_by_degree(c - 1) g.edges.find do |e| u,v = *e g[u].delete(v) g[v].delete(u) g._super_clique_exist?(e, c, {}, &found) end end def empty? verteces.empty? end def critical_subgraph_by_degree(d) g = self[verteces {|v| degree(v) >= d }] loop do prev_size = g.verteces.size g.verteces.keep_if {|v| g.degree(v) >= d } g.edges.keep_if {|e| e.all? {|v| g.verteces.include?(v)} } g.recreate_graph! if g.verteces.size == prev_size break elsif g.verteces.empty? break end end g end def verteces(&block) block.nil? ? @v : @v.select(&block) end def edges(&block) block.nil? ? @e : @e.select(&block) end def degree(i) @g[i].size end def adjacents(v) @g[v] end def [](v_or_vset) if v_or_vset.is_a?(Array) induced_subgraph(v_or_vset) elsif v_or_vset.is_a?(Integer) adjacents(v_or_vset) end end def induced_subgraph(vset) eset = edges {|e| e.all?{|v| vset.include?(v)} } self.class.new(vset, eset) end def inspect @g.inspect end end n, m = gets.split.map(&:to_i) V = n.times.to_a E = m.times.map { gets.split.map(&:to_i) } G = Graph.new(V,E) max_degree = G.verteces.map {|v| G.degree(v) }.max max_clique = nil if G.empty? max_clique = [] elsif G.edges.empty? max_clique = [G.verteces.first] else max_clique = G.edges.first (3 .. max_degree).bsearch do |k| !G.contain_clique?(k) do |clq| max_clique = clq if clq.size > max_clique.size end end end puts max_clique.size puts max_clique.sort.inspect
*1:ちなみに実装としては4は3の前に行っている
UnionFind木(簡易版/ruby)
すこし忘れていたのでメモ
rootで親をつなぎかえるのが肝。
class UnionFind < Array def initialize(n) super(n){|i| i} end def root(i) self[i] == i ? i : self[i] = root(self[i]) end def unite(i,j) self[root(i)] = root(j) end def same?(i,j) root(i) == root(j) end end
参考
ハドワイガー予想って
をマイナーとして含まないグラフは t-彩色可能 なのでしょうか?
もしかして対偶とって、t彩色可能でなければ、少なくとものマイナーを含むにすればよい?
だとするとそれに含まれる臨界グラフの頂点は全て次数t以上で、頂点数はt+1以上となるから、頂点がt+1となるまで縮約するとすれば、必ずとなるしかたがあるかな? なりそうな気はする。
つか、細分だけ考えれば、出次数の話だけだわ。
あとは縮約か。
最大クリークの。。。
最大クリーク数をcとすると、の確率で最大クリークと一致する順序が得られるのか。。。同じサイズの極大クリークあればもっと良い確率になるけど。。
とりあえず下記でできる気がしてきた。
1. サイズcのクリークは次数c-1以上の頂点がc個必要(条件A)なので、次数c-1以上の頂点を出して誘導グラフを作ってというのを再帰的に行う。最終的にすべての頂点の次数がc-1以上になる。
2. 頂点数がcならこの時点でサイズcのクリークが見つかった。頂点数がcより多ければ、最大クリークを探すアルゴリズムを実行(それが課題なんだけどcarraghanのアルゴリズムでもよいか)。
3. やはりサイズcのクリークがなければ、cをひとつへらしてやり直し
かな。FPTになってる気がするので、1を終えた段階のグラフG'に対してにはなる。
縮約していいのかな?
上記ポストの中で下記のような式がわかったわけだけど、この左辺のの部分を縮約してよいのだろうか?という疑問がいま頭をよぎっている。
基本的にはなら影響しないので、が接続する頂点の内、最大の頂点が彩色数を上げた頂点の場合、そこに縮約して構わないとおもうのだけど、縮約した点に接続する後続の点の扱いで、どうやればうまく縮約できるのかがまだよくわかっていない。
縮約って難しいな。
Brooksの定理++
無向グラフGの頂点を適当に順序付けして、辺の両端がなら、へ方向付けした有向グラフをHとする。
Hの最大出次数のとき、Gはk+1彩色可能で、これはBrooksの定理を含んで、より上限を押さえるとおもってるんだけど、既知なのかがわからん。
これは既知だった。これはk-degenerate graph(縮退)というらしい。
Degeneracy (graph theory) - Wikipedia
証明自体はたぶん正しいとおもう。
n頂点からなる単純な無向グラフをとし、に頂点を一つ追加したグラフをとする。
の彩色数の時、は、の次数により次のいずれかとなる。
証明については下記リンク先を参照*1
kousuke.hatenablog.com
これは結局、グラフに1点追加したとき、彩色数は2つも3つも上がらないし、接続する次数が彩色数未満なら確実に上がらないし、全点に接続すれば1上がるし、その間はよくわからんということに他ならない。ただ、グラフGをある空間から別の空間に頂点を一つずつ移動していくようなオペレーションを考えれば、移動先の彩色数と移動する頂点の辺の片側(移動先側)だけ見ていればよい、そうすればおよそ上限がわかってくるよということになる。
単純な無向グラフGの頂点集合Vを順序付ける写像fを用意する。
である頂点をと書くことにする。
無向グラフGから有向グラフHへの変換をとする。
hはfにより辺の向き(i > jならi -> jの方向)が一意に決まることを示している(つもり)。
としからを除く差集合をと書く。
のによる誘導部分グラフを、またからを除く部分グラフをと書く。
頂点vでの次数、出次数をそれぞれ、最大次数、最大出自数についてはと書く。に対しては、,である。
最初の式を書きなおすと以下のようになる。とする。
後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。
n = 0のとき、なので、はで彩色可能なことがわかる。
さてをを満たす数列とすれば、ステップ関数を使用して、もうすこし精度よく上限を求めることができる。
計算量はHに対してででき、上限は最悪でもで抑えることができる。
いままでの内容を例としてまとめるとこんな感じになる。(n=4の時の図)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
0 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 4 | |
0 | 1 | 2 | 3 | 2 | 2 | 2 | 3 | - | |
3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | - | |
3 | 4 | 3 | 7 | 4 | 3 | 3 | 3 | - | |
7 | 7 | 7 | 7 | 4 | 3 | 3 | 3 | - | |
0 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 4 |
まずブルックスの定理での彩色数の上限がなのに対して、で抑えられていることがわかる。
次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。また実際に彩色数も上がっていないことがわかる。
結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。
例えば、頂点を次数降順でソートするととなるが一番次数の大きい頂点はでその出次数はとなり、彩色数を0から1にするだけになる。むしろ重要なのは次数降順の場合、となるような部分グラフで全体の彩色数を求められるということだとおもう。
頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。
現在、厳密に彩色数を求める計算量はらしいけど、頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。
そこで重要になるのが、ヒューリスティックな方法で、今回の例ではが彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。
貪欲彩色のWelsh-Powellのアルゴリズムに比べると実際に彩色するかしないかの違いがある。ただ単に彩色数を近似したいときは今回紹介したほうが便利で、実際に彩色した結果がほしいのであればWelsh-Powellの方が便利。
となった時点で、いったん厳密な彩色数を求めてを更新して、もう一度となった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。
その他
例えば、ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。
シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。
位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。
追記
Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。
また上記の近似解kを使ってgales-sharpleyの変形で外部性のある安定結婚問題として解くとk以下の彩色が求められる。
計算量はだとおもうけどこれは少し怪しい(で収束するかが微妙)。
外部性があってもDA方式(受入保留方式/gales-sharpleyのアルゴリズム)で安定マッチング(ペア安定マッチング)はあることがわかっているけど、グループ安定性を満たさない、耐戦略性を満たさないというのが下記論文に書いてある。