Inclusion--Exclusion Algorithms for Counting Set Partitions (Part 2)

一人輪講

A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.

ほったらかしにしてた続き．

多項式空間

前回の方法では，空間計算量は指数オーダーだったが，空間計算量を節約して多項式オーダーに収める事が出来る．Vのある部分集合SがP（頂点集合Vの冪集合の部分集合）に含まれるかどうかを判定するための時間計算量によって，全体の時間計算量が変わる．

(1)2^{n}|P|n^{O(1)}
Pが多項式空間・多項式遅延で数え上げられる時．
（多項式遅延：1つの解を出力してから次の解を出力するまでの計算時間が入力の大きさの多項式である）
(2)3^{n}n^{O(1)}
ある部分集合がPの要素であるかのチェックが多項式時間で可能な時．
(3)\sum_{i=0}^{n}{n \choose i}T_{P}(i)
T_{P}(i)がサイズiの集合を数えるためにかかる時間で，それを多項式空間で計算可能な時．

グラフ彩色

彩色数\chi(G)：隣接する頂点には相異なる値を与える写像V\rightarrow \{1,\cdots,k\}が存在する最小のk
彩色多項式P(G;k)：正しいk-彩色の数（使う色数はk未満でもよい）

\chi(G)は2^{n}n^{O(1)}で計算可能

Iを独立集合の族とする．ただし，空集合は含めない．この時，\chi(G)はIによるk-被覆可能なkの中で最小のものに等しい．また，0-被覆は必ず不可能で，n-被覆は必ず可能である（Iには，頂点1つからなる集合が含まれている）．従って，low=0，high=nを初期値とし[k-被覆の個数 > 0]を条件とする二分探索を行えば\chi(G)を求めることが出来る．

また，彩色多項式については以下が成立する．
P(G;k) = \sum_{r=1}^{k}\frac{k!}{(k-r)!}p_{r}(I)
ただし，p_{k}(I)は，Iによるk-分割の数．
\frac{k!}{(k-r)!}p_{r}(I)は，グラフをr-彩色する方法の総数を数えている．
（論文ではこの式が誤植っぽい）

支配数

\delta(G)：各集合がGを支配しかつ互いに素となるようなk-分割が存在する最大のk

頂点集合S \in VがGを支配する：Vの全頂点はSの頂点と高々1の距離を持つ．言い換えると，Sの頂点とその隣接頂点でVを被覆する．

最大化問題では，k-被覆ではなくk-分割を使う（らしい）．

\delta(G)は2^{n}n^{O(1)}で計算可能．

Iを独立集合の族とする．この時，\chi(G)はIによるk-分割可能な最大のkに等しい．k-分割の個数は2^{n}n^{O(1)}で計算可能．従って，[k-分割の個数 > 0]という条件で二分探索を行えば良い．

実は，彩色数の近似アルゴリズムや，支配数の多項式空間アルゴリズムもあるけれど省略．

戯言

k-被覆は色々と使えそう．独立集合による被覆を考える場合，極大のもののみを考えればいいので，極大独立集合を列挙し，それらを使って頂点集合を圧縮すればちょっと速くなりそう．
k-分割はDPのオーダーがでかいので，SRM 388 Medium InformFriendsでもギリギリだった．
どうでもいいが，論文ではSという文字を色々な用途に使っていたので混乱した．