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

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

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(' ')}"