独立集合の個数を求めるアルゴリズムを紹介します。最大独立集合を求めるアルゴリズムと似ています：記事。
頂点集合について部分集合を全て試した \(O^*(2^n)\) を改善していきます（\(n\) : 頂点数）。
半分全列挙と高速ゼータ変換 : \(O(n2^{0.5n})\)
\(|A|=\lfloor n/2 \rfloor, |B|=n-|A|, V = A \coprod B\) となる頂点集合 \(A,B\) で頂点集合 \(V\) を２等分します。頂点 \(1, \ldots, n\) に対して変数 \(x_1, \ldots, x_n\) を割り当て、
$$f(x_1,\ldots,x_n) := \sum_{S \subset A\ \text{s.t. } S\text{ is independent set.}} \prod_{i \in S} x_i$$$$g(x_1,\ldots,x_n) := \sum_{S \subset B\ \text{s.t. } S\text{ is independent set.}} \prod_{i \in N[S]} x_i$$とします。\(f\) は \(A\) の独立集合の項を集めた多項式、\(g\) は \(B\) の独立集合とその隣接頂点の項を集めた多項式です。\(V\) の独立集合の個数は
$$f(x_1,\ldots,x_n)g(x_1,\ldots,x_n) \bmod (x_1^2,\ldots,x_n^2)$$の係数の和と等しいです。\(f,g\) の項は次のように累積和で書けます：
$$ \text{\(S\) is independent set}= \bigwedge_{\{i,j\} \subset S}\{i,j\} \not\in E(G),$$$$ N[S] = \bigcup_{\{i\} \subset S} N[i]$$ 従って、高速ゼータ変換により、\(f,g\) は \(O(n2^{n/2})\) で求まります。subset convolution を変形すると求めたいのは $$\sum_{S \subset B\ \text{s.t. } S\text{ is independent set.}} (\#\ \text{of}\ S \subset A\setminus{N[B]}\ \text{s.t. } S\text{ is independent set})$$です。\(\sum\)の中の項も高速ゼータ変換により \(O(n2^{n/2})\) で求まります。結局、全体でも \(O(n2^{n/2})\) で独立集合が求まりました。
全探索とメモ化 : \(O^*(2^{0.465n}), O^*(2^{0.426n})\)
効率的に分岐して、全探索します。連結と仮定して一般性を失いません。最大次数 2 以下のとき、パスかサイクルで、独立集合の個数は多項式時間で求まります。最大次数が 3 以上とします。グラフ \(G\) の独立集合の個数を \(f(G)\) と置くと \(f(G) = f(G-v) + f(G-N[v])\) が成り立ちます（\(N[v]\) は \(v\) とその隣接頂点の集合）。右辺１項目は \(v\) を独立集合に含まない場合、２項目は \(v\) を独立集合に含む場合です。最大次数 3 以上より \(G-N[v]\) の頂点数は \(n-4\) 以下です。つまり、頂点数 \(n\) のときの計算量を \(T(n)\) とすると、\(T(n) = T(n-1) + T(n-4)\) が成り立ちます。解くと、\(T(n) = O^*(2^{0.465n})\) です。更に、\(0.0869n\) 頂点以下の誘導部分グラフに含まれる独立集合の個数をメモ化すると、\(O^*(2^{0.426n})\) になります（計算量解析は最大独立集合の記事参照）。
Comments