2017-06-02

最大クリーク問題(改)

最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。

補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。

補グラフをk彩色できたら、 $O(k^2)$ かけてで色クラスを2つ選んで最大マッチングで最小頂点被覆を求めて、最大独立集合を求めて少しずつ大きくしていく。
もしk=2になったら確定する。

k≧3から落ちなければ、微妙。ただ、ある程度の大きさまで来たら、補グラフの連結性を判定して細切れの補グラフ連結成分の元グラフのクリークサイズで足し合わせることができるので、そこがカーネルになるなら、それはそれであり。

補グラフを彩色するのは最適彩色じゃなくてよいので、Welsh-Powellの貪欲彩色とか、外部性のある安定結婚問題とかで解ける。
むしろ最適だとn/kに近くなっちゃうので、頂点数最大になるような方法の方がよい。まあ、その方法はNP完全なんだけどね。

2017-06-02

P≠NP予想が嫌い

P≠NP予想 - Wikipedia

多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。

別にP=NPでもP≠NPでもどっちでもよいし、世の中的にはP≠NPの方が安全なのは知ってるけど、傲慢な感じがして嫌。

まあ、たぶんP=NPだけどね。

追記

今の自分の感触でいくと、最大クリーク問題だとグラフが大きくなればなるほど多項式に近くなるイメージがある。なのでNP=ZPPっていわれる方がしっくりくる。平均的には多項式で終わるが、最悪はもっとかかる(指数時間)がイメージには近い。

2017-05-29

続(4) - 最大クリーク問題

多分4じゃないかと思う。ナンバリングは適当

グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wを $n_i, m_i, w_i$ とすると下記が成り立つ
$n = \sum_{i=1}^k n_i \\ m = \sum_{i=1}^k m_i \\ w = \sum_{i=1}^k w_i + \sum_{i \ne j} n_i n_j$

補グラフが非連結も同様
$n = \sum_{i=1}^k n_i\\ m = \sum_{i=1}^k m_i + \sum_{i \ne j} n_i n_j\\ w = \sum_{i=1}^k w_i$

すげぇコンパクトになるんですけどって感じだ。

これが何につながるかというと最大クリーク問題なわけで、例えば頂点数100で、補グラフが $K_2 * 50$ のような非連結のグラフのとき、元のグラフではサイズ50のクリークが $2^{50}$ 個あるわけだけど、補グラフで考えると一気に頂点2 * 連結成分50の問題になる。

とはいえ、きっとよく知られた内容だとおもうんだけど、自分的にはこれは結構すごいなと感動した。

2017-05-25

巡回セールスマン問題

最大クリーク問題は改善があって、これでいいってところまで来たので一旦終わり。

巡回セールスマン問題でなんとなくアイデアが湧いて、葉指定 + k-best最小全域木問題に帰着できないかな?とおもっている。
ハミルトン閉路から一本辺取り除いたら道だけど、木の一種と思えば、次数数えるだけで道か?木か?はわかる。
有向辺なら実際にたどればよいし、コストあれば貪欲にいけるんじゃね?

って思っている。

2017-05-10

最大クリーク問題の現在

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

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

様々な全域木問題 from tmaehara

www.slideshare.net

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

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

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

凸関数どうやって作ればよいか悩んだ。

最初は二分探索してて、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

2017-05-08

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

いろいろ考えてるけど、最大クリーク問題は主に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/1271432はRubyでは最速になってた。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

2017-05-02

補グラフでの最小頂点被覆ってなんだろう?

補グラフでの最小頂点被覆ってなんだろう?って考えてて、最大クリークの頂点以外の頂点集合って意味しかないのかな