Joeの精進記録

旧：競プロ練習記録

Finding Near-Optimal Independent Sets at Scale

arxiv.org

Yoichi Iwataに教えてもらった、MIS最強系の論文。Exactなアルゴリズムではないが、最適解がわかっているデータセットで軒並み最適解を出していて強い。

Kernelに遺伝的アルゴリズムを使用することを再帰的に行うアルゴリズム

Evolutionary Algorithm

  1. 良さそうなIndependent Setの集合をいくつか見つける。
  2. グラフの2-way-partitionを見つける。つまりseparatorを見つける
  3. separateされた2要素を混ぜ合わせたものもIndependent Setになっている。これをmaximalにして、さらにARWアルゴリズムによって局所最適にする

これらを繰り返し、閾値以上の連続失敗で打ち切り

Kernelize

Akiba & Iwataのやつ。

  1. Pendant degree 1のやつを確定させ、隣接のものを削除
  2. degree 2-Folding 次数2の頂点があって、その隣接2頂点間に辺がないなら、foldできる
  3. LP LPで解の上限を計算する。LPを解かなくても2部グラフのmaximum matchingで代用できる
  4. Unconfined 忘れた
  5. Twin なんだっけ
  6. Alternative 初耳
  7. Packing Akiba & Iwataのやつやな

Algorithm

f:id:xuzijian629:20191219064425p:plain

まあ機械学習的には、上のアルゴリズムの

select \mathcal{U} \subset \mathcal{I}の部分が次数をみているだけの適当っぽいので、ここを良くする、というアイデアはあるが、普通にクソ遅そう

研究がまた先行研究とかぶった話

まあ別に初めてではないのであれなんですが

今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、

先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて、

しかもその先行研究の先行研究は、分野外（ハードウェア系）の最適化問題で現れた問題で、完全に界隈外の学会だったので

まったく気づきませんでした。

30年ほど昔の研究でした。

GNNの研究をしていると最近の論文しかないため、論文をサーチすれば何ができていて何ができていないかは比較的簡単に分かるのですが

離散最適化など、何十年にも渡って研究されているトピックの場合、あまり世に広まっていない論文だと

全然気づかないこともあるみたいですね。

反省として、こういうときは論文ではなく教科書を先にサーベイすべきです。

東大の図書館、実は本郷にきてから初めて利用したのですが

教科書が無限にあってすごい（それはそう）

ところで、担当してもらっていた先生から励ましの言葉をもらいました

Finding a paper working in your problem is not a bad news at all. It is a process of shaping your topic to the latest one. I am sure that the ideas you have got so far will be applied to solve some research problem soon.

これまでわりと一人で研究をしてきたのでこういう言葉を初めてかけてもらった気がします。

涙がでちゃって、あーやっぱ悔しかったんだなあと客観的に思ってしまいました。

一人ってよくないですね。

ツイッターで言語不明瞭をしちゃうし。

ちなみにこのトピックですが、一応先行研究との差集合は存在するのでそれで続けるという方針はあるのですが

いま客観的にみても、メインの主張がすでに言われているので、まったく同じ分野だとあまりインパクトあることは言えないかなあ

という気持ちになっています。

まあ人生の記録としてブログに

not-all-equal-3sat系証明のテクニック

グリッドグラフの描画とか、horizontalとverticalしか使っちゃだめ系描画など、一般に「自由度が相対的に制限される」ようなセッティングにおける可能性判定の証明に使える気がする。

証明のテクは、「必ずこの配置しかありえない」ような配置を組み合わせ、これから追加できる要素の配置を一通りに制限する。

not-all-equal-3satのインスタンスを目的のアルゴリズム(NP-Completeであると証明したいもの)を使って解くことを考える。

not-all-equal-3satの本質は、各clauseについて、すべてをtrueにしてはいけないということで、上述したような、配置が固定されるオブジェクトをうまく組み合わせ、 n - 1個の隙間に要素を敷き詰めるような設定を作る。これで、もし目的のアルゴリズムで敷き詰めが可能かどうか判定できるならnot-all-equal-3satが解けてしまう、という流れにする。

Complexity dichotomy on partial grid recognition

arxiv.org

ウ　ン　チ　ー　コ　ン　グ　！

グリッドに描画できるグラフのクラスをいろいろ考えて、PolynomialなものとNP-Completeなものに分けた。一般の描画はNP-Complete(そもそも木が無理なので)

次数が Dの要素のみからなるグラフを D-Graphとよぶことにする。たとえばパスグラフは {0, 1}-Graphで、サイクルは {2}-Graphである。

f:id:xuzijian629:20191218074122p:plain

雑感

詰めるところは一応あって

  • 三角形グリッドならどうなるか
  • 次元上げたときにどうなるか

でもこれやってて楽しいか？という気持ちになった。

www.amazon.co.jp

この本にめちゃめちゃ乗ってそうだしサーベイ漏れがないかこれでチェックして絵

The Complexity of Minimizing Wire Lengths in VLSI Layouts

タイトル練り直せ

www.sciencedirect.com

Theorem

最大次数が4の木をグリッドに埋め込めるかはNP-Complete

証明

not-all-equal 3satに帰着する。これは、3CNF式が与えられたときに、各clauseに少なくともひとつfalseになるリテラルが含まれるように充足可能か、という問題。

つまり、3CNF式が与えられたときに、それから最大次数が4の木を構成し、木がグリッドに埋め込める iff not-all-equal 3satの充足が存在する、という感じにしたい。

準備

以下のような木は向きの自由を無視して、一意な埋め込みがあります。また、これをつなげたもの（右）も一意な埋め込みになります。

f:id:xuzijian629:20191218041231p:plain

3SATから木を構成

f:id:xuzijian629:20191218041844p:plain

n個の変数が存在するとして、横に n + 2個、上下に長さ m + 1の骨格をつくる。骨格の端は、これから先に追加する枝の方向を確定させるためのもの（必ず横向きになるように）。

ここから、間の n列について、clauseからなる制約を付け加えていく。具体的には、 j番目のclauseに x_iが登場しない場合、対応する箇所（下画像参照）に横棒(striker)を一つ足す。

f:id:xuzijian629:20191218041404p:plain

さて、こうして構成されたグラフについて、グリッドに埋め込めるかどうかと、もとのCNF式にnot-all-equal-3sat充足が存在するかが等価になることを示す。

ポイントとしては、間の n列に関して、上下を逆にしてもグラフとして同型ということである。また各骨格について、左右反転させたものも同型になるという点が重要である。結果的にある埋め込みが存在したとき、上になっている方をTrue, 下になっている方をFalseとした充足が存在することになる。

さて、各clauseについて、変数は3つある( xと \bar{x}があれば無視できるので、異なる変数が3つ、と考えて良い)ので、各行について、clauseに登場しない変数分として n - 3本のstrikerが存在する。これについて、各変数がもしすべてtrueの場合、3本のstrikerが追加され、 n本のstrikerになってしまう。一方、そうでない場合、strikerは n - 1本以下である。

いま、strikerを埋め込める箇所は、free columnと呼ばれる n - 1箇所しかない。したがって、もしnot-all-equal-3satが充足可能でない場合、平面埋め込みが存在しない。

逆にnot-all-equal-3satが充足可能である場合、trueのものを上にし、falseのものを下にした場合、上述する性質を満たすような埋め込みが存在する（証明終了）

ウ　ン　チ　ー　コ　ン　グ

一応背景としては、木をmaximum edge length(とは?)を最小化して埋め込みたい、というものがあったっぽい。さすがに追わないと思う。 あと、complete binary treeで一意なうめこみがあるものがあるらしく(31頂点とか。ほかはしらんけどまあ似たような感じでしょ)、その場合についても本定理を拡張できるらしい。しらんけど。

ウ　ン　チ　ー　コ　ン　グ　！

Partial Grid

http://www.graphclasses.org/classes/gc_440.html

判定はNP-Completeでした。

arxiv.org

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！

ウ　ン　チ　ー　コ　ン　グ　！