Joeの精進記録

旧：競プロ練習記録

A Faster Parameterized Algorithm for Treedepth

木分解上のDPによってtreedepthを求める。

アルゴリズム自体が結構むずかしく、正当性は非自明

木分解上の各bagは、「そのbag以下の部分木のbagのUnionに含まれるノードについてのtreedepth decompositionのpartial decomposition」をもつ。partial decompositionのdepthとそのtreepdepth decompositionのdepthは同じ。

これを、nice tree decompositionのintroduce/forget/joinについて遷移規則を定めている。 forgetはかなり愚直だが、introduce, joinについては、自分より大きいdecompositionを考えるので、partial decompositionを得るために一度、特定のサイズ以下の頂点数の木をすべて生成したりして、かなり計算量がやばそう（だけどFPTなので定義上セーフ）

ここに超忖度を要するスライドがある

Computing Tree-Depth Faster Than $2^n$

タイトルの通り

アルゴリズムの概略は以下の通り

f:id:xuzijian629:20200229132652p:plain

ほぼ愚直な $O*(2^n)$ アルゴリズム $\mathbb{A}_0$ があり、アルゴリズムの探索空間を狭めた、 $\mathbb{A}_\varepsilon$ を構築して、大部分の問題を解く。

うまく行かない場合のグラフは、任意のminimalな分解がproblematic node $v$ を含む形になっている。

f:id:xuzijian629:20200229132849p:plain

グラフは上図のような分解になっていて、 $Y = Q \cup R_1$ を全探索して、さらに $R_1$ も全探索して、コーナーケースに相当する場合を解く。コーナーケースに含まれる小さな部分木 $Q_i$ と $R_j$ のtreedepthは前計算されているか、たかだか1回 $\mathbb{A}_0$ を適用して求めることができる。

部分木のtreedepthが分かっている状態で、 $Q_i$ , $R_1$ の順番を入れ替えて最適なもの（これはtreedepthに一致することが示される）を探したいが、これは多項式時間でも止まる。

最後の最後にすごい定義が効いていてすごい

木幅が1のグラフの木分解と動的計画法

普通に木DPをします。

ei1333.hateblo.jp

DDCC2020参加記

NHK杯で羽生結弦を（オンサイトで）見ていたら予選出れなかった

じょえくんとしてDDCCに参加していません
— 卒論に内容はいらない！🐄 (@ei1333) January 25, 2020

うしくんもぐもぐ笑

これはなに？

たぷりすたべる

Minimum Feedback Vertex Setの乱択アルゴリズム

Feedback Vertex Set (FVS)とは、グラフ $G$ の頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。

最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知られています。

この前NIIでwataさんに会ったときにかなり単純なアルゴリズムを教えていただいたのでまとめておきます（調べてもありえないぐらいヒットしなくて困りました）。

問題を判定問題として扱うために、入力はグラフ $G$ と整数 $k$ とし、 $G$ が大きさ $k$ 以下のFVSをもつか、を判定することにします。 $G$ の単純性は仮定しません。

Reduction

$G$ の最小次数を3以上にするために以下の操作を繰り返します。

頂点 $v$ がself-loopをもつ場合、その頂点を削除し、問題の $k$ を1減らす。
多重度3以上の辺がある場合、多重度を2にする。
次数が1以下の頂点がある場合、削除する。
次数2の頂点 $v$ がある場合、 $v$ を削除し、 $v$ につながっていた2頂点を新たに辺で結ぶ。
$k$ が負なら"No"を返してアルゴリズムを終了する。

すげー命題

最小次数が3以上のグラフ $G$ について以下が成り立つ。任意のFVS $X$ について、 $G$ の半数より多くの辺が $X$ に含まれる頂点を端点に持つ。

乱択アルゴリズム

上述した命題により、reductionを適用したグラフにおいて、一様ランダムにひとつ辺を選び、さらに一様ランダムにその端点を選ぶ（これは次数に比例してランダムに頂点を選ぶことと等価です）と、その頂点は1/4より大きい確率でFVSに含まれる、ということです。

なので、以下の乱択アルゴリズムを構成することができます。

「reductionを適用したグラフ $G$ において、閉路がなくなるまで、 $G$ での次数に比例した確率で頂点を $k$ 個まで順番に選んで削除し、閉路がなくなったらYesを出力する。閉路がなくならなかったらNoを出力する」

このアルゴリズムは、判定問題の答えがYesのとき、少なくとも $4^{-k}$ の確率でYesを返します。

参考：

https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (101ページあたり)

う　し　た　ぷ　に　き　あ　く　ん　笑　（スター稼ぎ用）

卒論名言集

1年前の卒論関連のSlackを見返していたらわりと面白かったのでまとめます

ちなみに締切は2/1だったみたいです。

1/19

DDCCの装置実装部門の話で盛り上がっている

1/20

けんしん「またライブラリの闇と戦っていたら1日が終了しかけている」

1/21

f:id:xuzijian629:20200121162623p:plain

f:id:xuzijian629:20200121162615p:plain

f:id:xuzijian629:20200121162711p:plain

（ラボ内締切というか、校正が必要なので初稿を1/24までに出してくださいみたいな話だった気がします）

1/22

ぼくがこどふぉで黄色になってやっとDiv2 & えづほから開放される

1/23

f:id:xuzijian629:20200121162914p:plain

1/24

f:id:xuzijian629:20200121162937p:plain

けんしんがnumpyの仕様と一日中戦っていた

f:id:xuzijian629:20200121163049p:plain

1/25

f:id:xuzijian629:20200121163204p:plain

1/26

f:id:xuzijian629:20200121163241p:plain

1/27

けんしんがインフル新薬の耐性菌のせいで熱が続いていてまだ登校できない問題

f:id:xuzijian629:20200121163414p:plain

1/28

けんしんの熱が下がる

f:id:xuzijian629:20200121163446p:plain

やっと実験結果が出たらしい

じょえたぷにきあくん笑が初稿を提出する。30枚5800 words

1/29

熱は下がったけど登校できないけんしん

f:id:xuzijian629:20200121163610p:plain

1/30 締切前日

やっとけんしんが登校。ほぼ大学にいたのであんまりSlackで話したことがない

2/1 締切

必死すぎてSlackの投稿が皆無。たぶんけんしんは一晩で2000 wordsぐらい生成してそう

define-by-runじゃないと困る問題

Hanjun-Daiのgraphnnがdefine-by-runじゃないせいで困った

複数グラフの、頂点ごとの確率を推論して、CrossEntropyしたい状況

batchあたりのlossを定義するために入力は複数グラフ(ひとつずつやってlossを足すということはできない)
グラフごとにCrossEntropyを計算したい
グラフの最大ノード数を固定したくない
でもsoftmaxするときに最大ノード数でreshapeしたい
muriyarokonnnan