Fourier meets Möbius: fast subset convolution

Details Fourier meets Möbius: fast subset convolution Fourier meets Möbius: fast subset convolution

2006-11-21

arxiv.org/abs/cs/0611101v1

Computer Science

Data Structures and Algorithms

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Fourier meets Möbius: fast subset convolution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fourier meets Möbius: fast subset convolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fourier meets Möbius: fast subset convolution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338525