2017-04-07

P=NPだと夢がある。

kousuke.hatenablog.com
頂点に関して $k-2t$ は極大グラフが１つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。

あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。
これは一緒に補グラフの最大独立問題をやってるに等しい。

少なくとも、NP完全問題が難しいのは、頂点に関するものと辺に関するものを両方一緒にやるからというのが現在の認識。
全部辺の問題に還元しながらやっていくのがたぶんよい。

追記
下記の資料をみていて、葉最大全域木でなんかインスピレーション湧いた。

様々な全域木問題 from tmaehara

www.slideshare.net

補グラフの辺は $\frac{v(v-1)}{2} - m$ なんで、これを0に近づけていくと良いし、葉最大で葉を指定するのは難しいけど、次数使って辺をうまく重みづけできそうだし、その最小全域木に沿って処理できれば、Dinkelbach algorithmで結構高速にできそう。

追記2
最大クリーク問題である条件下で、多項式時間で計算量一気に短縮できる処理があって、それを常に続けられると多項式時間になるのになぁとおもっている。

2017-04-04

最大クリークの計算量とか

修正しました。
kousuke.hatenablog.com

(以下、古い内容)

$\omega_k(G)$ をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)

最大サイズkのクリークを含む、単純な無向グラフ $G (|V| = n, |E| = m)$ があるとする。頂点vに隣接している頂点の集合を $adj(v)$ とし、 $e = \{u, v\}$ に対し、 $V_e = adj(u) \cap adj(v)$ とする。 $V_e \ne \emptyset$ ならば、eを含むサイズ3のクリークが存在し、誘導部分グラフ $G[V_{e} \cup e]$ の中にeを含むクリークが全て含まれる。よって次式が成り立つ。

$\omega_k(G) = \max_{e \in E}\,\{\, \omega_{k}(G[ V_e \cup e ]) \, \}$

$V_{e}$ の頂点はすべてeに接続しているので、 $G[ V_{e} ]$ にサイズk-2のクリークがあればよいので、さらに次式のように変形できる。

$\omega_k(G) = \max_{e \in E} \> \{ \> \omega_{k - 2}(G[ V_{e} ])\, \}$

前式により $\omega_k$ は再帰的に求めることができることがわかる。

先程の $V_e$ の表記を拡張して、単にサイズcのクリークを $C_{|c|}$ と表記し、その全点から接続している頂点の集合を $V_{|c|}$ と書くことにすると、再帰の深さtを用いて次のように変形できる。

$\omega_k(G) = \max_{C_{|2t|} \, \subset \, G} \> \{ \omega_{k - 2t}({G}[ V_{|2t|} ]),\hspace{2ex} 2t \le k \}$

$G[V_{e} \cup e]$ にサイズkのクリークが含まれない場合、eを消しても最大クリークには影響しない。Gからi個の辺を除去したものを $G_i = G - \{e_0,e_1,\dots,e_{i-1}\}$ とすると次式のように変形できる。iは $G[ V_{|2t|} ]$ に含まれる辺の最小のインデックスの意。

$\omega_k(G) = \max_{C_{|2t|} \, \subset \, G} \> \{ \omega_{k - 2t}({G_i}[ V_{|2t|} ]),\hspace{2ex} 2t \le k\}$

終了条件も合わせて下記のようになる。

$\displaystyle \omega_0(G) = \text{always} \, 1\\ \omega_1(G) = \begin{cases} 1 \hspace{10em} (n \gt 0) \\ 0 \hspace{10em} (n = 0) \\ \end{cases}\\ \omega_2(G) = \begin{cases} 1 \hspace{10em} (m \gt 0) \\ 0 \hspace{10em} (m = 0 ) \\ \end{cases}\\ \omega_k(G) = \begin{cases} 0 \hspace{10em} (n \lt k) \\ 0 \hspace{10em} (2m \lt k(k-1)) \\ 1 \hspace{10em} (G = K_n ,\hspace{2ex} n \ge k)\\ \max \> \{\omega_{2t}(C_{|2t|})\, \omega_{k - 2t}({G_i}[ V_{|2t|} ]) \} \end{cases}\\$

深さk/2の有界探索木だとおもうので、そうすると $\mathbb{O}(2^{\frac{k}{2}}m)$ だとおもう。

これに加えてサイズkのクリークはk-1以上の次数を必ず持つので次数k-1未満の点を除去していってもなくならない。この処理を $f_{k-1}: G \rightarrow G'$ とすると下記が成り立つ*1。

$\omega_k(G) = \omega_k(f_{k-1}(G))$

この前処理の結果、次数がk-1未満の頂点は全てなくなる。特にkが最大クリークサイズよりそれなりに大きい場合は $f_{k-1}(G) = K_0$ となり、前処理の中で完全に解けることになる(FPT?)。

また辺を評価する処理が進むにつれて辺はなくなっていき次数がk-1未満になる点はその時点で除去できる。
そのため、すべての辺を評価しなくとも、各頂点で $d(v) - (k - 2)$ 個の辺だけ評価すればよい。

もうひとつパラメーターがあって、それが極大クリークの数になる。これをwとするとtに対し、w'≦wなんだけどこれを上手く処理できると多項式の目が出てくるかなと思っている。

補グラフの辺を変わりに評価対象にすればよいだろうか。

*1:これ自体は彩色問題でも成立する

2017-04-03

続々々最大クリーク問題(2)

すこしコードを変更している。興味ある人はpaiza.ioで動かしてみてほしい。
https://paiza.io/projects/14TYw6RR2KIPBLRjSNCPrg

V=1000、E=9988、20彩色可能、最大次数 69、次数の分布具合は下記のグラフを参考。
最大クリークは8。列挙しているわけではないので、複数ある可能性もある。
f:id:tinsep19:20170403232929p:plain

2017-03-29

続々々最大クリーク問題

基本的には前書いた内容。
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の前に行っている

2017-03-29

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

参考

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

2017-03-28

ハドワイガー予想って

lealgorithm.blogspot.jp

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

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

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

つか、細分だけ考えれば、出次数の話だけだわ。
あとは縮約か。

2017-03-17

最大クリークの。。。

最大クリーク数を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$ にはなる。