タイトルの通り
アルゴリズムの概略は以下の通り
ほぼ愚直なアルゴリズム
があり、アルゴリズムの探索空間を狭めた、
を構築して、大部分の問題を解く。
うまく行かない場合のグラフは、任意のminimalな分解がproblematic node を含む形になっている。
グラフは上図のような分解になっていて、を全探索して、さらに
も全探索して、コーナーケースに相当する場合を解く。コーナーケースに含まれる小さな部分木
と
のtreedepthは前計算されているか、たかだか1回
を適用して求めることができる。
部分木のtreedepthが分かっている状態で、,
の順番を入れ替えて最適なもの（これはtreedepthに一致することが示される）を探したいが、これは多項式時間でも止まる。
最後の最後にすごい定義が効いていてすごい
