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)- Vertex and edge covers with clustering properties: Complexity and algorithms
- An exact algorithm for subgraph homeomorphism
- Parameterized approximation via fidelity preserving transformations
- A faster parameterized algorithm for pseudoforest deletion
- Clifford algebras meet tree decompositions
- The parameterized complexity of the rainbow subgraph problem
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Improved Steiner tree algorithms for bounded treewidth
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Covering and packing in linear space
- Faster algorithm for optimum Steiner trees
- Capacitated domination faster than O(2ⁿ)
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Finding and counting vertex-colored subtrees
- Trimmed Moebius inversion and graphs of bounded degree
- Structurally parameterized \(d\)-scattered set
- Revising Johnson's table for the 21st century
- A generic convolution algorithm for join operations on tree decompositions
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Finding optimal triangulations parameterized by edge clique cover
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Inclusion/exclusion meets measure and conquer
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Iterative compression and exact algorithms
- Facility location problems: a parameterized view
- Width, depth, and space: tradeoffs between branching and dynamic programming
- A multivariate analysis of the strict terminal connection problem
- Faster exponential-time algorithms in graphs of bounded average degree
- Computing optimal Steiner trees in polynomial space
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Parameterized complexity of secluded connectivity problems
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Space saving by dynamic algebraization based on tree-depth
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Generalization of a Hadamard type inequality for permanents
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
- Sharp separation and applications to exact and parameterized algorithms
- Fast monotone summation over disjoint sets
- Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
- Finding a forest in a tree
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
- Automatic evaluations of cross-derivatives
- Graph minors and parameterized algorithm design
- The parameterized complexity of the rainbow subgraph problem
- Invitation to Algorithmic Uses of Inclusion–Exclusion
- Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
- Fast Möbius inversion in semimodular lattices and ER-labelable posets
- On directed Steiner trees with multiple roots
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Lossy kernels for connected dominating set on sparse graphs
- Treewidth and pathwidth parameterized by the vertex cover number
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
- Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Facility Location Problems: A Parameterized View
- Faster Steiner Tree Computation in Polynomial-Space
- Iterative Compression and Exact Algorithms
- Approaches to the Steiner Problem in Networks
- Partitioning into sets of bounded cardinality
- Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
- Covering Vectors by Spaces: Regular Matroids
- Subexponential parameterized algorithms
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Confronting intractability via parameters
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Definition and algorithms for reliable Steiner tree problem
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
- An Exact Algorithm for the Steiner Forest Problem
- A Survey on Spanning Tree Congestion
- Fast Algorithms for Join Operations on Tree Decompositions
- Patching colors with tensors
- scientific article; zbMATH DE number 7559420 (Why is no real title available?)
- Tensor network complexity of multilinear maps
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- On the Complexity of Bounded Context Switching.
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- Exact algorithms for minimum weighted dominating induced matching
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Lossy kernels for connected dominating set on sparse graphs
- Fourier inversion for finite inverse semigroups
- Parameterized complexity of directed Steiner tree on sparse graphs
- Scheduling partially ordered jobs faster than \(2^n\)
- Determination of Glycan Structure from Tandem Mass Spectra
- Complexity issues in vertex-colored graph pattern matching
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Counting perfect matchings as fast as Ryser
- Fast zeta transforms for lattices with few irreducibles
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- On the computational difficulty of the terminal connection problem
- Fixing knockout tournaments with seeds
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)
