Fourier meets Möbius: fast subset convolution
(2007) Annual ACM Symposium on Theory of Computing p.6774 Abstract
 We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of annelement 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 sumproduct ring can be computed in Õ(2n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a... (More)
 We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of annelement 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 sumproduct 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 maxsum or minsum 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 DreyfusWagner algorithm. We also discuss extensions to recent Õ(2n)time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006). (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/623051
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} ; Kaski, Petteri and Koivisto, Mikko
 organization
 publishing date
 2007
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Proceedings of the thirtyninth annual ACM symposium on Theory of computing
 pages
 67  74
 conference name
 Annual ACM Symposium on Theory of Computing
 conference location
 San Diego, California, United States
 conference dates
 00010102
 external identifiers

 scopus:35449001611
 ISBN
 9781595936318
 DOI
 10.1145/1250790.1250801
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 d23b076054e7470fa4233e7c167049ba (old id 623051)
 date added to LUP
 20160404 13:46:58
 date last changed
 20210506 19:28:10
@inproceedings{d23b076054e7470fa4233e7c167049ba, abstract = {We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of annelement 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 sumproduct 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 maxsum or minsum semiring in Õ(2n M) time.<br/><br> <br/><br> 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 DreyfusWagner 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 = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko}, booktitle = {Proceedings of the thirtyninth annual ACM symposium on Theory of computing}, isbn = {9781595936318}, language = {eng}, pages = {6774}, title = {Fourier meets Möbius: fast subset convolution}, url = {http://dx.doi.org/10.1145/1250790.1250801}, doi = {10.1145/1250790.1250801}, year = {2007}, }