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なので定義上セーフ）

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