Fourier meets M\"{o}bius: fast subset convolution
From MaRDI portal
Publication:3549598
zbMATH Open1232.68188arXivcs/0611101MaRDI QIDQ3549598FDOQ3549598
Authors: Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto 
Publication date: 5 January 2009
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).
Full work available at URL: https://arxiv.org/abs/cs/0611101
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)
Cited In (only showing first 100 items - show all)
- Facility location problems: a parameterized view
- Clifford algebras meet tree decompositions
- Computing optimal Steiner trees in polynomial space
- Title not available (Why is that?)
- Sharp separation and applications to exact and parameterized algorithms
- The parameterized complexity of the rainbow subgraph problem
- On the terminal connection problem
- Title not available (Why is that?)
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Title not available (Why is that?)
- Set multi-covering via inclusion-exclusion
- On the computational difficulty of the terminal connection problem
- A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
- Graph minors and parameterized algorithm design
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- An exact algorithm for connected red-blue dominating set
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Capacitated domination faster than \(O(2^n)\)
- Faster algorithm for optimum Steiner trees
- The Parameterized Complexity of the Rainbow Subgraph Problem
- Facility Location Problems: A Parameterized View
- A multivariate analysis of the strict terminal connection problem
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Finding and counting vertex-colored subtrees
- Faster exponential-time algorithms in graphs of bounded average degree
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Determination of Glycan Structure from Tandem Mass Spectra
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- On Directed Steiner Trees with Multiple Roots
- Approaches to the Steiner Problem in Networks
- Complexity issues in vertex-colored graph pattern matching
- Automatic evaluations of cross-derivatives
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
- Finding a Forest in a Tree
- Title not available (Why is that?)
- Treewidth and pathwidth parameterized by the vertex cover number
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Fast Möbius inversion in semimodular lattices and ER-labelable posets
- Faster Steiner Tree Computation in Polynomial-Space
- Trimmed Moebius inversion and graphs of bounded degree
- Title not available (Why is that?)
- An exact algorithm for subgraph homeomorphism
- Exact and approximate bandwidth
- Parameterized approximation via fidelity preserving transformations
- Computing rank-width exactly
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Iterative Compression and Exact Algorithms
- Generalization of a Hadamard type inequality for permanents
- Definition and algorithms for reliable Steiner tree problem
- Algebraic methods in the congested clique
- Title not available (Why is that?)
- A faster parameterized algorithm for pseudoforest deletion
- Structural parameterizations of clique coloring
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Complexity of Grundy coloring and its variants
- On the Complexity of Bounded Context Switching.
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Exact algorithms for minimum weighted dominating induced matching
- Inclusion/exclusion meets measure and conquer
- Iterative compression and exact algorithms
- An efficient tree decomposition method for permanents and mixed discriminants
- Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
- Scheduling partially ordered jobs faster than \(2^n\)
- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
- Title not available (Why is that?)
- An ETH-tight algorithm for bidirected Steiner connectivity
- Title not available (Why is that?)
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- Fast monotone summation over disjoint sets
- A generic convolution algorithm for join operations on tree decompositions
- Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
- Fourier Inversion for Finite Inverse Semigroups
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
- Title not available (Why is that?)
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Invitation to Algorithmic Uses of Inclusion–Exclusion
- Title not available (Why is that?)
- Computing generalized convolutions faster than brute force
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Parameterized complexity of secluded connectivity problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding optimal triangulations parameterized by edge clique cover
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples
- Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
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)
