Joeの精進記録

旧：競プロ練習記録

平面グラフで高速に動作するアルゴリズムで一般グラフの場合を学習する

テーマ案

これやってる人いるかな。普通に気になる。

平面グラフ from yutaka1999

www.slideshare.net

yutaka1999氏のスライドがあり、平面グラフ判定は本気を出すと $O(V)$ でできるなどと書かれていてびっくりする。

Max-Cut

e-archive.informatik.uni-koeln.de

平面グラフでのMax-Cutは $O(V^{1.5}\log V)$ らしい。速すぎ

Max-Cutのベンチマーク

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1941-09.pdf

現時点での最速？ http://mauricio.resende.info/doc/gmaxcut.pdf

数万頂点程度

実験するなら平面グラフと一般グラフの両方でやりたいね

平面グラフでもNP-hardな問題

ほとんど。。。Max-CliqueはPだけど自明すぎてア

Independent Set (Vertex Cover), Dominating Set, Feedback Vertex Set, Traveling Salesperson Problem...

Feedback Vertex Set

http://www.eda.ce.titech.ac.jp/ueno/Files/papers/TTU12-ICNC.pdf

Degree at most 3系ではいくつか簡単なアルゴリズムもあるっぽい

It is known that MinFVS is NP-hard for bigraphs while it can be solved in $O(n^5)$ time for chordal bipartite graphs, in $O(n^2m)$ time for convex graphs, and in $O(nm)$ time for permutation graphs.

らしい。すご（やっぱそんなにうれしくねえ）