Computing Tree-Depth Faster Than $2^n$

タイトルの通り

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

ほぼ愚直なアルゴリズムがあり、アルゴリズムの探索空間を狭めた、を構築して、大部分の問題を解く。

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

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

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

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