最大クリーク問題の現在

Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースで O^\ast(2^{\frac{k}{2}})がはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。

大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあった

www.slideshare.net




https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-53-638.jpg?cb=1363753229

最大クリークの計算量とか(続き) - 高温処理済みコースケでも書いてたのとほぼ同じ形になっていったため、この畳み込みの式をみて、方向性はわるくないことがわかった。

 \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}


https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-44-638.jpg?cb=1363753229

辺の重みは自分で作って、それを修正する形で最大クリークサイズをもとめればいいことに気づいた。
辺の重みは w(e) = |V_e| + 2にして、 |V_e| \ge \omega(G[V_e])の関係を利用する。


凸関数どうやって作ればよいか悩んだ。
https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-26-638.jpg?cb=1363753229

最初は二分探索してて、Dinkelbachにしたいんだけどって感じで。。。でも、g(t)を支える直線に沿って進むのがイメージしにくかったのと、比じゃないしとおもっていて困っていた。


結果、まあ納得いくソースになった。特に超denseのときにもつらくないのがよい。

判定ならn = 200, m = 4565, k = 14を探すのに2.74秒、プログラミングコンテストの問題とかでも行けそう。

$ time bin/max_clique -k 14 < fixtures/clique/N200M4565C14.txt
14
9 11 13 47 52 57 61 90 126 150 158 170 180 192

real    0m2.749s
user    0m0.030s
sys     0m0.015s

最大クリーク問題で面白いなとおもったこと

いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。
ある無向グラフGについて \omega(G)を最大クリークサイズを返す関数とする。

f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフを G_iとすると
 \omega(G) = \sum \omega(G_i)

g(m) : グラフが非連結で、連結グラフn個に分かれているとする、その各グラフを G_iとすると
 \omega(G) = \max \{ \omega(G_i) \}

h(k) : 頂点をうまく分割するとサイズkのクリーク c \in C^k( C^kはサイズkのクリークの集合)と、その全点から接続している頂点 V_cとそれ以外。

 \displaystyle \omega(G) = \omega(c^k) + \omega(G[V_c]) + \alpha, c^k \in C^k
 V_c = \emptyset となるのが極大クリーク。

上記を踏まえ、判定式 \omega_kをつくる

f(w)のうち、補グラフで孤立点(元のグラフでは自身を除く全点と接続)となっているものを取り出す処理をp(n)とする。 O(n)で処理できる。

 \displaystyle \omega_k(G) = \omega_a(A) + \omega_{k-a}(G [ V \setminus A ]), A = \{v \in V \,|\, d(v) = |V| - 1 \}

h(k)はk=2に固定した h_2 = \omega_2とp(n)と畳み込み使って、下記のように表すことができる。

 \omega_k(G) = \max_{e \in E} \{ \omega_2(e) + \omega_{k-2}(G[V_e]) \} = h_2 \ast p

g(m)については h_2が、Eを順次探索するのでその時に一緒にやってしまえる(実装では辺に対してBFS, クリークに対してDFSとなっている)のであまり考えなくてよい。f(w)の孤立点以外については実装は簡単(UnionFind)でできるけど、そのケースにどれくらい当てはまるかが微妙なのと補グラフの辺はもっていないので O(n^2)掛けてつくるかが微妙、濃度に合わせてやるのが良さそうという感じをもっている。

とりあえずABC002 派閥で試してhttp://abc002.contest.atcoder.jp/submissions/1271432Rubyでは最速になってた。C++と比べるとおそいけどスピンアップの時間考えるとかなり速いと思う。
Cのコード見てると隣接行列使って解いてるっぽいコードがあった。すげぇ早い

メモ: 下記の論文によると補グラフのBFSやDFSを O(n+M), m + M = \frac{n(n-1)}{2}でできるらしい。なら、やればよいかという気がしている。

http://www.orsj.or.jp/~archive/pdf/a_a/1995A_228.pdf

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

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式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を1本以上含んでいるので、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かもしれない。

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

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

グラフと補グラフの関係

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あるわ。

P=NPだと夢がある。

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

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

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


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

www.slideshare.net

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

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