blogoid

今回は木幅（tree-width）の話を書いてみようと思います。 木幅とは、大雑把に言うとグラフがどれだけ木に近いかを表す値です（木に近いほど小さな値になります）。NP困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部のNP困難な問題は、グラフの木幅が定数で上から抑えられるなら、…