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

続々々 最大クリーク問題

基本的には前書いた内容。
kousuke.hatenablog.com

1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。

動作

0. 頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で二分探索する。
1. contain_clique?で求めるクリークのサイズcを指定する。
2. subgraph_by_degreeで頂点の次数が全てc-1以上となるような部分グラフを探す。
3. super_clique_exist?で指定したクリーク(最初は辺e, サイズをkとする)を含む、サイズk+1の拡大クリークを探す。
3-1. 指定したクリークが求めるサイズのクリークならtrueを返して終了。
3-2. 拡大クリークがなければ、それは極大クリークで求めるサイズのクリークでないのでfalseを返して終了。
3-3. 拡大クリークの数 + 現在のクリークサイズ(最初は2)が、求めるクリークサイズc未満なら、その時点でサイズcのクリークには含まれないのでfalseを返して終了。
3-4. 3を再帰的に行って、サイズcのクリークを探す。
4. 辺eを削除する


簡単にいうと辺eを含む極大グラフ全体を評価していってダメなら、辺eを消すので辺eを含むクリークのサイズはだんだん小さくなっていく。
ただし辺eを削除しても他の辺e'で、e'を含む極大グラフ全体を評価するのに影響は与えない。(辺eに含まれるクリークは全部評価が終わっているから)。
基本的には計算量はeを含む極大クリークの数とその重複度合による。
ある辺eがサイズc未満の極大クリーク1つだけに含まれる場合、super_clique_exist?内で、3-2のケースにあたり枝刈される。同様に再帰が深くなっていっても、極大クリーク1つに確定できるようになった時点でサイズc未満なら枝刈できる。例えばCa,Cb,Ccの3つのクリークに含まれる辺eでも|Ca| + |Cb| < cならば、Ccに含まれない頂点を選択した時点で枝刈出来る。

ちなみに実装としては4は3の前に行っている。

全部のクリークを探すとかじゃないので、結構速いとおもう。
ただ計算量として2^cとかは含んでいるかもしれない。

もうすこし改良できる点。

二分探索をやるなかで、枝刈りしたところを何度も確認することになるので、枝刈時点のクリークと可能性のある最大サイズをキャッシュしておいて探すクリークのサイズが変更になったらそこから継続するとかすれば、もうすこし早くなりそう。

コード

class Graph
    def initialize(vset, eset)
        @g = {}
        @v = vset.to_a
        @e = eset.to_a
        @v.each{|v| @g[v] = []}
        @e.each{|u,v| @g[u] << v; @g[v] << u }
        @g
    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 = 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 subgraph_by_degree(d)
        g = self
        loop do
            prevsize = g.verteces.size
            g = g[g.verteces{|v| g.degree(v) >= d }]
            if g.verteces.size == prevsize 
                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
    alias :d :degree
    
    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 = @e.select{|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

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

参考

www.slideshare.net

ハドワイガー予想って

lealgorithm.blogspot.jp

 K_{t+1} をマイナーとして含まないグラフは t-彩色可能 なのでしょうか?

もしかして対偶とって、t彩色可能でなければ、少なくとも K_{t+1}のマイナーを含むにすればよい?

だとするとそれに含まれる臨界グラフの頂点は全て次数t以上で、頂点数はt+1以上となるから、頂点がt+1となるまで縮約するとすれば、必ず K_{t+1}となるしかたがあるかな? なりそうな気はする。

最大クリークの。。。

最大クリーク数をcとすると、 \frac{{}_n\mathrm{P}_c}{n!}の確率で最大クリークと一致する順序が得られるのか。。。同じサイズの極大クリークあればもっと良い確率になるけど。。

とりあえず下記でできる気がしてきた。

1. サイズcのクリークは次数c-1以上の頂点がc個必要(条件A)なので、次数c-1以上の頂点を出して誘導グラフを作ってというのを再帰的に行う。最終的にすべての頂点の次数がc-1以上になる。
2. 頂点数がcならこの時点でサイズcのクリークが見つかった。頂点数がcより多ければ、最大クリークを探すアルゴリズムを実行(それが課題なんだけどcarraghanのアルゴリズムでもよいか)。
3. やはりサイズcのクリークがなければ、cをひとつへらしてやり直し

かな。FPTになってる気がするので、1を終えた段階のグラフG'に対して 2^\sqrt{2m}nにはなる。

縮約していいのかな?

kousuke.hatenablog.com

上記ポストの中で下記のような式がわかったわけだけど、この左辺の \chi(G_n)の部分を縮約してよいのだろうか?という疑問がいま頭をよぎっている。
 \chi(G_n) > \Delta_+({H_n}^c) \Rightarrow \chi(G_n) = \chi(G)

基本的には d_+(v_{n}) < \chi(G_n)なら影響しないので、 d_+(v_{n})が接続する頂点の内、最大の頂点が彩色数を上げた頂点の場合、そこに縮約して構わないとおもうのだけど、縮約した点に接続する後続の点の扱いで、どうやればうまく縮約できるのかがまだよくわかっていない。

縮約って難しいな。

Brooksの定理++

無向グラフGの頂点を適当に順序付けして、辺の両端 i, j i \lt jなら、 i \leftarrow jへ方向付けした有向グラフをHとする。
Hの最大出次数\Delta_+(H) = kのとき、Gはk+1彩色可能で、これはBrooksの定理を含んで、より上限を押さえるとおもってるんだけど、既知なのかがわからん。

証明自体はたぶん正しいとおもう。

n頂点からなる単純な無向グラフをGとし、Gに頂点 vを一つ追加したグラフをG'とする。
Gの彩色数 \chi(G) = kの時、\chi(G')は、 vの次数d(v)により次のいずれかとなる。

 \chi(G')=\begin{cases} 
k+1 & ( d(v) = n ) \\ 
k+1 \text{ or } k & ( d(v) \ge k )\\
k   & ( d(v) \lt k )
\end{cases}

証明については下記リンク先を参照*1
kousuke.hatenablog.com

これは結局、グラフに1点追加したとき、彩色数は2つも3つも上がらないし、接続する次数が彩色数未満なら確実に上がらないし、全点に接続すれば1上がるし、その間はよくわからんということに他ならない。ただ、グラフGをある空間から別の空間に頂点を一つずつ移動していくようなオペレーションを考えれば、移動先の彩色数と移動する頂点の辺の片側(移動先側)だけ見ていればよい、そうすればおよそ上限がわかってくるよということになる。

単純な無向グラフGの頂点集合Vを順序付ける写像fを用意する。
 f:  \{ \> i \in \mathbb{N}_0 \> | \> i \lt |V| \> \}  \rightarrow V

 f(i)=vである頂点をv_iと書くことにする。

無向グラフGから有向グラフHへの変換を h: G \rightarrow Hとする。

 h:  \{ \> \{u,v\} \in E \> \}  \rightarrow \{ \> (v_{src}, v_{dst}) \in V \times V \> | \> src \gt dst \>\}

hはfにより辺の向き(i > jならi -> jの方向)が一意に決まることを示している(つもり)。
 V_n = \{ v_0, v_1, \dots, v_{n-1}\}とし Vから V_nを除く差集合V \setminus V_n{V_n}^cと書く。

 G,\> H V_nによる誘導部分グラフ G[V_n] ,\> H[V_n] G_n ,\> H_n、またG ,\> HからG_n, H_nを除く部分グラフG \setminus G_n, H \setminus H_n{G_n}^c,\> {H_n}^cと書く。

頂点vでの次数、出次数をそれぞれd(v),d_+(v)、最大次数、最大出自数については\Delta(G),\Delta_+(H)と書く。{G_n}^c,\> {H_n}^cに対しては、\Delta({G_n}^c)=\max \{ \> d(v), v \in {V_n}^c \> \},\Delta_+({H_n}^c)=\max \{ \> d_+(v), v \in {V_n}^c \> \}である。


最初の式を書きなおすと以下のようになる。 \chi(G_n)=kとする。

 \chi(G_{n+1}) - \chi(G_n) = \begin{cases} 
1 & (d_+(v_n) = n)\\ 
1 \text{ or } 0 & (d_+(v_n) \ge k)\\
0 & (d_+(v_n) \lt k)
\end{cases}

後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。

 \chi(G_n) > \Delta_+({H_n}^c) \Rightarrow \chi(G_n) = \chi(G)

n = 0のとき、 {H_n}^c = Hなので、 G \Delta_+(H)+1で彩色可能なことがわかる。

さて \chi_{n} \chi_{n} \ge \chi(G_n)を満たす数列とすれば、ステップ関数 u(x)を使用して、もうすこし精度よく上限を求めることができる。

\begin{cases} 
 \chi_{n+1} - \chi_{n} = u(d_+(v_n) - \chi_{n}) \\
 \chi_0 = 0 \\
\end{cases}

 u(x)=\begin{cases} 
1 & (x \ge 0) \\
0 & (x \lt 0)  
\end{cases}

計算量はHに対して O(|V|)ででき、上限は最悪でも \Delta_+(H)+1で抑えることができる。

いままでの内容を例としてまとめるとこんな感じになる。(n=4の時の図)
f:id:tinsep19:20170320145321p:plain

 n 0 1 2 3 4 5 6 7 8
 \chi(G_n) 0 1 2 3 4 4 4 4 4
 d_+(v_n) 0 1 2 3 2 2 2 3 -
 \Delta_+({H_n}^c) 3 3 3 3 3 3 3 3 -
 d(v_n) 3 4 3 7 4 3 3 3 -
 \Delta({G_n}^c) 7 7 7 7 4 3 3 3 -
 \chi_n 0 1 2 3 4 4 4 4 4

まずブルックスの定理での彩色数の上限が \chi(G) \le 8(= \Delta(G)+1)なのに対して、 \chi(G) \le 4(= \Delta_+(H)+1)で抑えられていることがわかる。

次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。また実際に彩色数も上がっていないことがわかる。

結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。
例えば、頂点を次数降順でソートすると d(v_n) = \Delta({G_n}^c) \ge \Delta_+({H_n}^c)となるが一番次数の大きい頂点は v_0でその出次数は d_+(v_0) = 0となり、彩色数を0から1にするだけになる。むしろ重要なのは次数降順の場合、\chi(G_n) \gt d(v_n)となるような部分グラフG_nで全体の彩色数を求められるということだとおもう。

頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。


現在、厳密に彩色数を求める計算量はO(2^nn)らしいけど、頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。

そこで重要になるのが、ヒューリスティックな方法で、今回の例では \chi_nが彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。

 \chi_n > d(v_n)となった時点で、いったん厳密な彩色数を求めて \chi_nを更新して、もう一度 \chi_n > d(v_n)となった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。

その他


例えば、ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。

シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。
位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。

Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。

*1:いろんな文書の中で見かけるんだけど、ちゃんと定式化?されてるのをみたことがない気がする

winptyってすごいんだな

SourceTree付属のgit-bashが便利で使ってるんだけど、rubyirbとかつかうと何か変になってるなぁって思ってたんだけど、winpty ruby -S irbで起動すればよいことに気が付いた。pryとかもこれでよくなるのかな。