Fourier meets möbius: fast subset convolution
By Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Symposium on the Theory of Computing, 2006
354 citations recorded by the source corpus.
We present a fast algorithm for the subset convolution problem:given functions <i>f</i> and <i>g</i> defined on the lattice of subsets of an<i>n</i>-element set <i>n</i>, 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<sup>2</sup> 2<sup>n</sup>) additions and multiplications, substanti y improving upon the straightforward O(3<sup>n</sup>) 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<sup>n</sup> 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<sup>n</sup> M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2<sup>k</sup> n<sup>2</sup> + n m) algorithm for the Steiner tree problem in graphs with <i>n</i> vertices, <i>k</i> terminals, and <i>m</i> edges with bounded integer weights, improving upon the Õ(3<sup>k</sup>n + 2<sup>k</sup> n<sup>2</sup> + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2<sup>n</sup>)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/b1edd28d54d1d84ed2a6c446695b22acffaaf2bf
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Handbook of Computational Social Choice (2016, methodology): “The fastest known algorithm for the agenda control problem for complete balanced trees is by Vassilevska Williams (2009) and runs in O(2poly(m)) time and uses sophisticated machinery such as fast subset convolution (Björklund et al., 2007).”
- Tracking the Footprints of Spin Fluctuations: A MultiMethod, MultiMessenger Study of the Two-Dimensional Hubbard Model (2020, neutral): “[170] A.”
- Lower bounds based on the Exponential Time Hypothesis (2011, methodology): “We can prove the hardness of Grid Tiling by a simple reduction from Clique.”
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time (2011, methodology): “To achieve these goals for vertices with colours 00 and 11 we do not specify the side of the cut and we use variants of the fast subset convolution [7] algorithm.”