Fourier meets möbius: 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 S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n 2 2 n ) additions and multiplications, substanti y improving upon the straightforward O(3 n ) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2 n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2 n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2 k n 2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3 k n + 2 k n 2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2 n )-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).

Authors

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski
• Mikko Koivisto

Keywords

• Möbius transform
• Steiner tree
• convolution