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

続々々 最大クリーク問題

基本的には前書いた内容。
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が接続している頂点の集合 V_u, V_vとする。
 (V_u \cap V_v)のどの頂点をeに加えてもサイズ3のクリークになり、これはサイズ3以上のクリークでも同様。
また辺eを含むクリーク全体は (V_u \cap V_v) \cup eのべき集合の中にある。


基本的には計算量は極大クリークの数とその重複度合による。

ある辺eがサイズc未満の極大クリーク1つだけに含まれる場合、super_clique_exist?内で、3-2のケースにあたり再帰なしに枝刈される。同様に複数の極大クリークに含まれていて、再帰が深くなっていっても、極大クリーク1つに確定できるようになった時点でサイズc未満なら枝刈できる。
他にも C_1,C_2,C_3の3つのクリークに含まれる場合(すべてサイズはc未満)でも |C_1 \cup C_2| < cならば、 C_3に含まれない頂点を選択した時点で枝刈出来る。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の前に行っている