Skip to content →

Subset Convolutionのアルゴリズム

集合の畳み込み(Subset Convolution)
$$(f * g)(S) := \sum_{T \subseteq S} f(T) g(S \setminus T)$$ を全ての部分集合 \(S \subseteq [n]=\{1,\ldots,n\}\) に対して列挙するアルゴリズムを紹介します[1, 2]。素朴な DP では \(O(3^n)\) ですが、 \(O(n^22^n)\) にできます。

\(n\) 変数多項式の積 \(F(x_1,\ldots,x_n)G(x_1,\ldots,x_n) \bmod (x_1^2,\ldots,x_n^2)\) を求める問題だと捉えれば、\(\mathbb{R}\) 係数や \(\mathbb{Z}/p\mathbb{Z}\) 係数(\(p\) : 素数)のときは FFT を使って \(O(n^2 2^n)\) を達成できます(多変数畳み込み(切り捨て))。しかし、環係数では逆元が存在すると限らないので FFT できません。この記事では環係数で \(O(n^2 2^n)\) を達成するアルゴリズムを扱います[1, 2]。

アルゴリズム[1]

元の個数を \(x\) のべき指数にした $$F(S)=f(S)x^{|S|}, G(S)=g(S)x^{|S|}$$ を定義します。また、条件を緩めた畳み込み
$$(F \star G)(S) := \sum_{U, V \subseteq S \\ U \cup V = S} F(U) G(V) $$を定義します。\(x\) の冪指数が \(U\) と \(V\) の(重複を込めた)元の個数を表しているので、求めたいのは$$(F \star G)(S) \bmod x^{|S|+1} = (f*g)(S)x^{|S|}$$ です。元の個数のみを保持して、どの元が \(U\) と \(V\) で重複したかを忘れています。情報を圧縮しているので、計算量削減が期待できます(同様のアイディアを使うアルゴリズム:多変数畳み込み(切り捨て))。

ゼータ元 \(\zeta\) を右から掛けると、
\begin{align}((F \star G) * \zeta) (S) =& \sum_{T \subseteq S}\ \sum_{U, V \subseteq T \\ U \cup V = T} F(U) G(V) \\ =&\sum_{U \subseteq S} F(U) \sum_{V \subseteq S} G(V) \\
\\ =& (F * \zeta)(S) \cdot (G * \zeta)(S) \end{align}となります。\(F \star G\) のゼータ変換が、\(F\) と \(G\) のゼータ変換の積になりました! 右からメビウス元 \(\mu\) を掛けると逆変換になり、$$(F \star G) (S) = (((F * \zeta) (G * \zeta)) * \mu)(S)$$ を得ます。高々 \(n\) 次の多項式を値に取る関数 \(F, G\) の高速ゼータ変換、高速メビウス変換をすればよいので、計算量は \(O(2^nn^2)\) です。

このような、元の個数を持ったゼータ変換・メビウス変換を [1] では ranked zeta transform, ranked M¨obius transform と呼んでいます。

アルゴリズム[2]

[2]では(同じ式を)別の角度から見たアルゴリズムが設計されています。 \(S \subseteq [n-1]\) とします。\([n-1]\) の冪集合に定義域を制限した \(F_0 (S):= F|_{2^{[n-1]}}(S)\) と \({n}\) を加えた、\(F_1(S) := F|_{2^{[n-1]}}(S \cup \{n\})\) を定義します。\(G_0, G_1\) も同様に定義します。すると漸化式$$ (F \star G)(S \cup \{n\}) = ((F_0 + F_1) \star (G_0 + G_1))(S)-(F_0 \star G_0) (S) $$が成り立ちます。集合のサイズが1減少したかわりに、畳み込む関数の係数の次数が1つ増えました。つまり \(F \star G\) を列挙する問題は

  • \(F_0 \star G_0\) for all \(S \subseteq [n-1]\)
  • \((F_0+F_1) \star (G_0+G_1)-F_0 \star G_0 \) for all \(S \subseteq [n-1]\)

を列挙する部分問題に帰着できます。

部分問題への帰着を繰り返した時の計算量を求めましょう。係数が高々 \(k\) 次の関数の畳み込み (\(\star\)) を、\(n\) 元集合の全ての部分集合について列挙する計算量を \(T(n,k)\) とすると、\(T(n,k)=2T(n-1,k+1)+O(n)\) が成り立ちます。\(O(n)\) は多項式の引き算の計算量です。求めたいのは \(T(n,0)\) でした。漸化式を繰り返し適用して、\(T(n,0)=2^nT(0,n)+O(n^22^n)\) を得ます。\(T(n,0)\) は高々 \(n\) 次多項式の積の計算量ですから、 \(T(n,0)=O(n^22^n)\) です。

実装例 : 再帰, 非再帰

複数回の subset convolution

複数回の subset convolution は各点積で一度に計算してしまえます。つまり
$$(f_1*f_2*\cdots*f_m)(S) = \prod_{S=\bigsqcup U_i} f_i(U_i)$$とすると、
$$((F_1 \star F_2 \star \cdots \star F_m) * \zeta) (S) \\
=(F_1 * \zeta)(S) \cdot (F_2 * \zeta)(S) \cdot \cdots \cdot (F_m * \zeta)(S) $$となります。

証明:\(m=2\)の場合はすでに示しました。\(m=k-1\)で成立を仮定します。次のように \(m=k\) のとき、\(m=k-1\) に帰着できるので帰納法により証明終了。$$\begin{align}&((F_1 \star (F_2 \star F_3\star \cdots \star F_k)) * \zeta) (S)\\
=&(F_1 * \zeta)(S) \cdot ((F_2 \star F_3\star \cdots \star F_k) * \zeta)(S) \end{align}$$

各点積は、FFT のような多項式のアルゴリズムが使えます。また、subset の足し算・引き算は ranked Zeta transform した後も足し算・引き算です。従って、例えば subset の exp を求めたいとき、ranked Zeta transform してから、多項式の exp を求めるアルゴリズムが使えます。

練習問題

【問題1】 グラフ \(G\) が与えられる。\(G\) の彩色数が \(m\) 以下であるか判定せよ。

【解答】頂点集合 \(S\) が独立集合であるとき、\(f(S)=1\) さもなくば \(f(S)=0\) となる関数 \(f\) を用意します。\(f\) の subset convolution の \(m\) 乗を求めればよいです。\(m\) 乗を各点積で行うことにより、\(n\) を頂点数として \(O(2^nn^2)\) です。

※\(m\) が定数である場合、より効率的なアルゴリズムが存在しないか検討するべきです(例:ABC 199 問題D)。

【問題2】 グラフ \(G\) が与えられる。すべての誘導部分グラフ \(G[S]\) に対して、\(G[S]\) の全域部分グラフの個数を求めよ。(出典:熨斗袋さん

【解答】指数型母関数の問題21で解説しています。

参考文献

  1. Fourier Meets Mobius: Fast Subset Convolution
  2. 指数時間アルゴリズム入門
  3. Library Checker : Subset Convolution

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA