ヒューリスティックな彩色

k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。

あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続したグラフを作って、それを彩色してやるとkになって間違っていることがわかるとかないかなとかおもった。

最大出次数を最小にする順序/Rubyのpriority queue

kousuke.hatenablog.com

以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。

Degeneracy (graph theory) - Wikipedia

アルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。


Rubyの優先度付キューを探してみると標準では優先度付キューはないようだ。lazy priority quueuというgemがあって、この中でベンチマークがある。

github.com

優先度変更がなくてよいならPriorityQueueCxx、 変更有りならsupertinou/PriorityQueue、どちらもC++ extensionなので、Pure Rubyならlazy_priority_queueがよいよとのこと。

サンプルやコードを見ていると、なるほど優先度を高くする方向(min heapでは、値としては下がる方向)はサポートできるみたいな感じっぽい。

ヒープのデータ構造に違いがあり、lazy_priority_queueは2項ヒープとのこと、フィボナッチヒープと比べると、フィボナッチヒープの方が平均的には早いけど、ワースト時間で遅いものがあるみたいな感じっぽい。さきのC++拡張の2つともフィボナッチヒープ。

二項ヒープ - Wikipedia

フィボナッチヒープ - Wikipedia

多分2007年度の卒業論文(学部生)じゃないかと思うんだけど、グラフの彩色アルゴリズムの内容も基本的にはk-degenerationグラフの順序を求めているのと一緒だった。強いてあげるならば、なるべく次数降順に並ぶように順序を決めていた。

自分としてはここに安定結婚問題をもってきたいとおもっていて、適当につくったのが、結構いい値がでてて、精度保障できないかなとか思ってるけど、全然証明とかできない。

貪欲法と違うのは基本的に1色で塗れるだけ塗るというのをやってる。安定結婚問題に合わせて色を男性、頂点を女性とすると、貪欲法だと女性優先で、下記のコードだと男性優先なんじゃないかとおもっているが実際には貪欲法と変わらない。なんというか、うまいこと頂点毎の順序や色ごとの順序つくれないかなとおもっている。なんで安定結婚問題でやりたいかといえば、マッチングの質に関しての研究が進んでいるからというのが理由。意外と順序決めるのが早かったりしないかなとおもっている。

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

def degeneracy_order(graph, vset)
  q = MinPriorityQueue.new
  k = 0
  order = []
  used = {}
  d = {}
  vset.each do |v|
    dv = graph[v].size
    d[v] = dv
    q.push v, dv
  end
  until q.empty?
    v = q.dequeue
    used[v] = true
    k = d[v] if d[v] > k
    order << v
    graph[v].each do |u|
      d[u] -= 1
      unless used[u]
        q.change_priority u, d[u]
      end
    end
  end
  order.reverse
end

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

def gs_coloring(graph, vset_order)
  match = {}
  c = -1
  until vset_order.empty?
    c += 1
    vset_order.reject! do |v|
      if graph[v].none?{|u| match[u] == c }
        match[v] = c
      end
      match[v]
    end
  end
  [c + 1, match]
end

opt_result = false

opt = OptionParser.new
opt.on('-r','print result.'){ opt_result = true }
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 = build_graph(V,E)
vset_order = degeneracy_order(G, V)
number, result = gs_coloring(G, vset_order)

puts number
puts V.map {|v| "#{v} #{result[v]}" } if opt_result

最大クリーク問題(改)

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

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

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

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


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

P≠NP予想が嫌い

P≠NP予想 - Wikipedia

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

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

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

追記

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

続(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の問題になる。

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

巡回セールスマン問題

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


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

って思っている。

最大クリーク問題の現在

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