最大クリークの計算量とか(続き) - 高温処理済みコースケ

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