Fourier meets M\"{o}bius: fast subset convolution
From MaRDI portal
Publication:3549598
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)- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Fast Möbius inversion in semimodular lattices and ER-labelable posets
- Confronting intractability via parameters
- Faster Steiner Tree Computation in Polynomial-Space
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Finding and counting vertex-colored subtrees
- On the computational difficulty of the terminal connection problem
- Automatic evaluations of cross-derivatives
- Capacitated domination faster than \(O(2^n)\)
- Faster algorithm for optimum Steiner trees
- Counting perfect matchings as fast as Ryser
- Inclusion/exclusion meets measure and conquer
- Facility Location Problems: A Parameterized View
- Structural parameterizations of clique coloring
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Approaches to the Steiner Problem in Networks
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
- Treewidth and pathwidth parameterized by the vertex cover number
- A faster parameterized algorithm for pseudoforest deletion
- On the terminal connection problem
- An exact algorithm for subgraph homeomorphism
- Fast zeta transforms for lattices with few irreducibles
- Determination of Glycan Structure from Tandem Mass Spectra
- Lossy kernels for connected dominating set on sparse graphs
- Iterative compression and exact algorithms
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Parameterized approximation via fidelity preserving transformations
- Facility location problems: a parameterized view
- Trimmed Moebius inversion and graphs of bounded degree
- Iterative Compression and Exact Algorithms
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Clifford algebras meet tree decompositions
- Exact and approximate bandwidth
- Complexity issues in vertex-colored graph pattern matching
- On the Complexity of Bounded Context Switching.
- Computing rank-width exactly
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Computing optimal Steiner trees in polynomial space
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- A multivariate analysis of the strict terminal connection problem
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
- Generalization of a Hadamard type inequality for permanents
- An efficient tree decomposition method for permanents and mixed discriminants
- Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Graph minors and parameterized algorithm design
- scientific article; zbMATH DE number 7559420 (Why is no real title available?)
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- Finding a forest in a tree
- Sharp separation and applications to exact and parameterized algorithms
- Faster exponential-time algorithms in graphs of bounded average degree
- On directed Steiner trees with multiple roots
- Exact algorithms for minimum weighted dominating induced matching
- Definition and algorithms for reliable Steiner tree problem
- The parameterized complexity of the rainbow subgraph problem
- Subexponential parameterized algorithms
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Scheduling partially ordered jobs faster than \(2^n\)
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- The parameterized complexity of the rainbow subgraph problem
- An exact algorithm for connected red-blue dominating set
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Parameterized complexity of secluded connectivity problems
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
- Set multi-covering via inclusion-exclusion
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- Space saving by dynamic algebraization based on tree-depth
- Finding optimal triangulations parameterized by edge clique cover
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Parameterized complexity of directed Steiner tree on sparse graphs
- Computing generalized convolutions faster than brute force
- Fast Algorithms for Join Operations on Tree Decompositions
- An Exact Algorithm for the Steiner Forest Problem
- A generic convolution algorithm for join operations on tree decompositions
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
- A Survey on Spanning Tree Congestion
- The parameterized complexity of the survivable network design problem
- Fixing knockout tournaments with seeds
- Covering Vectors by Spaces: Regular Matroids
- Invitation to Algorithmic Uses of Inclusion–Exclusion
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- scientific article; zbMATH DE number 7764113 (Why is no real title available?)
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Fast monotone summation over disjoint sets
- Lossy kernels for connected dominating set on sparse graphs
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
- Tensor network complexity of multilinear maps
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
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)
