最大クリークの。。。
最大クリーク数を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のアルゴリズム)で安定マッチング(ペア安定マッチング)はあることがわかっているけど、グループ安定性を満たさない、耐戦略性を満たさないというのが下記論文に書いてある。
Facebookは恐ろしいよね。
最大クリーク問題 試行
いままでと全然変えてみてある辺(i,j)を含む、順序上 j以下の頂点で構築できる最大クリークとか考えてみた。
サイズcのクリークがある時、全点から接続している点はc+1のクリークって考えると凄くコンパクト。
でも2^cとか含むだろうけどね。
n,m = gets.split.map(&:to_i) G = {} U = {} V = n.times.to_a E = m.times.map do gets.split.map(&:to_i).sort end E.sort! V.each do |v| G[v] = [] U[v] = [] end E.each do |from, to| G[from] << to G[to] << from U[to] << from end MEMO = {} def dfs(clique, c) clique.sort! s,t = clique.first, clique.last status = clique.join(' ') return MEMO[status] if MEMO[status] nclique = clique.inject(U[t]){|n, v| n & G[v] }.sort nc = nclique.empty? ? c : nclique.map {|nv| dfs(clique + [nv], c+1) }.max p clique: clique, c: nc MEMO[status] = nc end E.each do |e| puts "#{e} #{dfs(e, 2)}" end
なんとなくこのコードが引っかかる。
再帰呼び出しc回でサイズcの極大クリークが見つかる、サイズcのクリークは2^c - 1個のクリークがあるけど、なんとなくうまく枝刈りするとサイズがcの極大クリーク(他のクリークに含まれないの意味)をc^2のオーダーで抜けれそうな気がするんだよね。
例えばこんな感じのコードかなぁ。
n,m = gets.split.map(&:to_i) VISITED = {} G = {} V = n.times.to_a E = m.times.map { gets.split.map(&:to_i).sort } V.each {|v| G[v] = [] } E.each do |from, to| G[from] << to G[to] << from end def dfs(clique, max) clique.sort! status = clique.join(' ') return max if VISITED[status] VISITED[status] = true if clique.size > max max = clique.size # p clique: clique, max: max end head, *body = clique nclique = body.inject(G[head]){|n, v| n & G[v] } if clique.size + nclique.size > max max = nclique.inject(max) {|m, u| dfs(clique + [u], m) } end max end if n == 0 puts 0 elsif m == 0 puts 1 else puts E.inject(0){|max, e| dfs(e, max) } end
下記入力に対して
8 14 0 1 0 2 0 3 1 2 1 3 2 3 0 4 0 5 0 6 0 7 4 7 4 5 5 6 6 7
こういう動き
{:clique=>[0, 1], :max=>2} {:clique=>[0, 1, 2], :max=>3} {:clique=>[0, 1, 2, 3], :max=>4} {:clique=>[0, 1, 3], :max=>4} {:clique=>[0, 2], :max=>4} {:clique=>[0, 3], :max=>4} {:clique=>[1, 2], :max=>4} {:clique=>[1, 3], :max=>4} {:clique=>[2, 3], :max=>4} {:clique=>[0, 4], :max=>4} {:clique=>[0, 5], :max=>4} {:clique=>[0, 6], :max=>4} {:clique=>[0, 7], :max=>4} {:clique=>[4, 7], :max=>4} {:clique=>[4, 5], :max=>4} {:clique=>[5, 6], :max=>4} {:clique=>[6, 7], :max=>4}
サイズcのクリークの全点から接続している点は必ずサイズc+1のクリークで、これまでに見つかった最大クリークのサイズをmaxとすると、サイズc+1のクリークがmax - c個より多く存在しないとmax + 1のサイズのクリークはないので枝刈ってみた。
Submission #1100279 - AtCoder Beginner Contest 002 | AtCoderの結果
これcarraghanのアルゴリズムっぽい。。。
https://www.jstage.jst.go.jp/article/ciqs/2006/0/2006_0_JP04/_pdf
あけましておめでとうございます。
本年もよろしくお願いします。
昨年は最大クリーク問題で頭イタイ人に思われたりして、一時期、心を病んだ状態でしたが、すごく楽しかったなぁとおもっています。
ことしも全然やるつもりで、まさにブログ名どおりの高温処理済みになったなぁとおもっています。