Fourier Meets Mobius: Fast Subset Convolution

We present a fast algorithm for the subset convolution problem: given functions f and g defined on the lattice of subsets of an n-element set N, compute their subset convolution f * g, defined for all S subset of N by (f * g)(S) = Sigma(T subset of S)f(T)g(S\T), where addition and multiplication is carried out in an arbitrary ring. Via Mobius transform and inversion, our algorithm evaluates the subset convolution in O(n(2) 2(n)) additions and multiplications, substantially iniproving upon the straightforward 0(3(n)) algorithm. Specifically, if the input functions have an integer range {-M, -M+1, ..., . All), their subset convolution over the ordinary sum-product ring can be computed in (O) over tilde (2(n)log M) time; the notation (O) over tilde suppresses polylogarithmic factors. Furthermore, using a standard embedding technique we can compute the Subset convolution over the max-sum or main-sum semiring in (O) over tilde (2(n) M) time. To demonstrate the applicability of fast subset convolution we present the first (O) over tilde (2(k)n(2) + nm) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the (O) over tilde (3(k)n+2(k)+nm) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent (O) over tilde (2(n))-time algorithms for covering and partitioning problems (Bjorklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).