彩色数を求めるアルゴリズム

このスライドを読めばだいたいわかります

個人的に詰まったところメモ

最初の言いかえ

グラフ $G = (V, E)$ が $k$ 彩色可能 $\Leftrightarrow V$ を $k$ 個の独立集合で被覆できる

について, $k$ 個の独立集合は直交していなければいけないというような条件はない（それはそうで, $k$ 彩色で $k$ 色全部使わなくてもいいので同値）

独立に $k$ 個選ばないといけないと思っていたので, その後の

$f(S) = I(S) ^ k$

が重複しまくりやんけとなっていたが問題なかった

そのためこの $g(S)$ は彩色多項式 $P(G, k)$ とは異なる (ですよね？)

$P(G, k)$ を求めたかったらサイズの総和を $|V|$ で固定してあげればよくて, そうすると $f(S)$ はどうするんでしょうか

$I(S,n) =$ $S$ の部分集合で大きさ $n$ の独立集合の数を求められれば二次元DPにできそうな気分です

それはともかく後は頑張って $I(S)$ を求めればいい

独立集合の数え上げだが, $v \in S$ として

のどちらかなので,

$I(S) = I(S - {v} - adj(v)) + I(S - {v})$

と書ける

ということで, あとはbitDPを書くだけですね

おしまい