2017-04-30

最大クリークの途中で補グラフが出てくる話

kousuke.hatenablog.com
前回、ワーストケースで $\mathbb{O}(2^{\frac{k}{2}}(m - \frac{k-2}{2} n))$ になると書いた。

FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか?
簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。

最大クリーク判定の式をおさらいする。 $A$ は自身を除く全点に接続している頂点。
$\displaystyle \omega_k(G) = \begin{cases} 0 & (n \lt k) \\ 0 & (2m \lt k(k-1)) \\ \omega_{k - a}(G[ V \setminus A ]) & (A \ne \emptyset) \\ \max_{e \in E} \> \{ \, \omega_{k - 2}(G[ V_{e} ])\, \} & \\ \end{cases}$

3番目をA式、4番目をB式と呼ぶ。

A式では全点につながった辺はまとめて処理でき、ここは分岐する必要がない。また、この処理で辺は一気に減っているけど、補グラフの辺は実は減ってない。このことからも極大クリークを示すのに適当そうな感じがする。またA式の処理により、B式を処理するときには、すべての頂点は必ずどこかの頂点とつながっていない。そのため、補グラフに辺がある。ということでここから補グラフで展開していく。

補グラフの辺の数をwとする。 $w = \frac{n(n-1)}{2} - m$ となる。

D式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を１本以上含んでいるので、D式処理後、必ず補グラフの辺は2つ以上減る。
計算量はざっと $O(2^{\frac{w}{2}}(m-\frac{k-2}{2}n))$ が想定される。
とはいえワーストケースがk/2で収まるので、準指数 $O(2^{\sqrt{2w}}(m-\frac{k-2}{2}n))$ でも大きそう。

なのでP=NPか、P≠NPでも、比較的小さいところで $\log w$ より小さくなる関数じゃないかとおもっている。もしかすると虚数がでてきて、k/2とどちらか速い方の可能性もある。

最小頂点被覆の計算量で $C^n \ge C^{n-1} + C^{n-3}$ が示せればよいとしてCを求めるやつだと、そのままwに置き換えると $C^w \ge C^{w-2}$ になるんで $C \ge 1$ か、1ならP=NPかもしれない。

2017-04-26

最大クリークの計算量とか(続き)

kousuke.hatenablog.com
大事なことに気が付いたので、前回の修正。

単純な無向グラフ $G(V,E) \, ,(|V| = n, |E| = m)$ に対し、 $\omega_k: G \rightarrow \mathbb{R}$ をサイズkのクリークが含まれるかどうかを判定する関数とする。

$\begin{cases} \omega_k(G) \gt 0 & \text{true} \\ \omega_k(G) \le 0 & \text{false} \\ \end{cases}$

グラフGに自身を除く全頂点に接続する頂点がある場合、それらは必ず最大クリークに含まれる。そのような頂点集合を $A = \{ \, v \in V \, | \, d(v) = |V| - 1 \}, |A| = a$ とすると、下記が成り立つ。

$\omega_k(G) = \omega_{k - a}(G[ V \setminus A ]) \tag{1}$

$A = \emptyset$ の場合を考える。
頂点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} ])\, \} \tag{2}$

終了条件も含め、下記のようになる。

$\displaystyle \omega_1(G) = \begin{cases} 1 & (n \gt 0) \\ 0 & (n = 0) \\ \end{cases}\\ \omega_2(G) = \begin{cases} 1 & (m \gt 0) \\ 0 & (m = 0 ) \\ \end{cases}\\ \omega_k(G) = \begin{cases} 0 & (n \lt k) \\ 0 & (2m \lt k(k-1)) \\ \omega_{k - a}(G[ V \setminus A ]) & (A \ne \emptyset) \\ \max_{e \in E} \> \{ \, \omega_{k - 2}(G[ V_{e} ])\, \} & \\ \end{cases}$

また $G[ V_e \cup e ]$ にサイズkのクリークが含まれない場合、Gからeを取り除いても最大クリークには影響しない。

$\omega_{k-2}(G[V_e])$ は辺を評価していると見ることができる。 $f : E \rightarrow \mathbb{N_0}, f(e) = |V_e|$ とする。

$f(e) \lt k - 2$ であれば、即座にその辺を除去する前処理を行う。この前処理の結果、少なくともサイズ3のクリークをk-2個以上含む辺のみが残り、各頂点の次数はk-1以上になる。

また次数がk-1未満になる頂点はその時点で除去できる。そのため、前処理後のグラフに対し、すべての辺を評価しなくともよい。

評価する辺の集合が最小のものを $E_{min}, |E_{min}| = m_{min}$ とし、 $E_{min}$ を取り除いたグラフを $H(V,E \setminus E_{min})$ とする。
下式よりおよそ $m - \frac{k - 2}{2}n$ の辺を評価すれば良いことがわかる。

$E_{min} = \{ e \in E \, | \, \forall v \in V \rightarrow d_{H}(v) < k - 1 \}$
$m_{min} \ge \frac{1}{2}\sum_{v \in V} \{d(v) - (k - 2)\} = m - \frac{k - 2}{2}n$

最悪でも深さk/2の有界探索木だとおもうので $O(2^{\frac{k}{2}}(m - \frac{k - 2}{2}n ))$ の目がある。

~~結局FPTなんだけど、~~そのパラメーターは極大クリークの数に依存する。上記のワーストケースは常に $A = \emptyset$ の場合で、どんなにクリークサイズが大きくても、完全グラフ-数辺みたいのだとあっという間に終わる。

前回は全点に接続する頂点を書いてなくて、終了条件に完全グラフって書いてたけど、これでぐっと見通しがよくなった。

次は補グラフでの最大独立集合を考えることにする。

$f(e) \lt k - 2$ を使った前処理の実装例

#!/usr/bin/env ruby
require 'optparse'

def shave_by_clique(g, eset, c)
  eset.reject {|u,v| (g[v] & g[u]).size < c }
end

def build_graph(g,vset,eset)
  vset.each {|v| g[v] = [] }
  eset.each {|u,v| g[v] << u; g[u] << v }
end

c = 3
opt = OptionParser.new
opt.on('-c C', 'lower number bounds of 3-cliques.'){|v| c = v.to_i }
opt.parse!(ARGV)

n, m = gets.split.map(&:to_i)
V = n.times.to_a
E = m.times.map { gets.split.map(&:to_i) }
G = {}
eset = E
build_graph(G,V,E)

loop do
  shaved = shave_by_clique(G, eset, c - 2)
  if eset.size == shaved.size
    break
  end
  G.clear
  build_graph(G, V, shaved)
  eset = shaved
end

vset = eset.flatten.uniq.sort
index = {}
vset.each_with_index{|v,i| index[v] = i }

puts "#{vset.size} #{eset.size}"
puts eset.map{|e| e.map{|v| index[v] }}.map{|e| e.join(' ')}
puts "# #{vset.join(' ')}"

2017-04-08

グラフと補グラフの関係

kousuke.hatenablog.com

n頂点の完全グラフを $K_n$ 、独立グラフ(頂点のみで辺がないグラフ)を $I_n$ とする。

n頂点のグラフ $G_n$ がある。
このとき $K_n$ から $I_n$ へひとつづつ辺を消していく順序集合のうち、 $G_n$ を含む順序の集合 $F_{G_n}$ を定めることができる。

このとき $F_{G_n}$ のどの順序を通っても $G_n$ の補グラフ $G_n^\ast$ はない。
そのため $K_n \rightarrow G_n \rightarrow I_n \rightarrow G_n^\ast \rightarrow K_n$ のような構造を考えることができる。

$K_n$ の辺の数は $\frac{n(n-1)}{2}$ で $I_n$ と位相が $\pi$ ずれていて、 $2\pi$ で $K_n$ に戻るので、上の構造は $e^{i\frac{4\pi\,m}{n(n-1)}}$ と同相と考えることができそう。
同様に $G_n,G_n^\ast$ も位相が $\pi$ 離れているとみることができそう。

また最大クリーク問題を考えると頂点がなくなる方向 $K_0$ への順序集合(こちらは頂点集合)もある。
最大クリーク問題の解は $K_n \rightarrow I_n$ と $G_n \rightarrow G_n^\ast$ の方向が一致することができる最大のnとみることができる。
なんとなくグラフを複素数の多項式として表せるんじゃないかとおもっていて、上の式を頂点方向と辺方向で全微分とかすると、その極大値が最大クリークにならないだろうかとかおもっていたりする。

またイメージとしては $K_0, K_n, I_n$ に対し、 $K_0 -> K_0$ への自己ループの輪( $e_{loop}$ )と $K_n, I_n$ を結ぶ輪が通っており、 $e_{loop}$ が縮もうとするときの緊張関係のように考えることができそう。

追記

ないとおもったけど、同型ならあるんだよね。 $K_{1,2}$ とか考えると同型なら $K_3 \rightarrow I_3$ のなかに $K_{1,2}^\ast$ あるわ。

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の前に行っている