Fourier meets M\"{o}bius: fast subset convolution

Authors Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Publication date 5 January 2009

Full work available at URL https://arxiv.org/abs/cs/0611101

Steiner tree problem covering and partitioning problems subset convolution problem

Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 Ssubseteq N by (f * g)(S) = sum_{T subseteq S}f(T) g(Ssetminus 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).

Cited in

(only showing first 100 items - show all)

This page was built for publication: Fourier meets M\"{o}bius: fast subset convolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549598)