Fourier meets Möbius: fast subset convolution

Summary, in English

We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-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(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) 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 Õ(2n 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 Õ(2n M) time.



To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2k n2 + 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 Õ(3kn + 2k n2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2n)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).

• Author: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Department/s: Department of Computer Science; Computer Science; Parallel Systems
• Publishing year: 2007
• Language: English
• Pages: 67-74
• Publication/Series: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
• Links: http://dx.doi.org/10.1145/1250790.1250801
• Document type: Conference paper
• Topic: Computer Science
• Conference name: Annual ACM Symposium on Theory of Computing
• Conference date: 0001-01-02
• Conference place: San Diego, California, United States
• Status: Published
• Project: Exact algorithms
• Research group: Algorithms
• ISBN/ISSN/Other: ISBN: 978-1-59593-631-8