Approximation algorithms for some parameterized counting problems
From MaRDI portal
Recommendations
- On the parameterized complexity of approximate counting
- Randomized Approximations of Parameterized Counting Problems
- Counting problems in parameterized complexity
- The Parameterized Complexity of Counting Problems
- On the relative complexity of approximate counting problems
- Approximate counting and NP search problems
- The relative complexity of approximate counting problems
- Parameterized counting problems
- Parameterized counting problems
Cited in
(48)- On counting 3-D matchings of size \(k\)
- Randomised enumeration of small witnesses using a decision oracle
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Parameterized random complexity
- Finding and counting vertex-colored subtrees
- The parameterised complexity of counting connected subgraphs and graph motifs
- A fixed-parameter perspective on \#BIS
- Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
- The parameterized complexity of maximality and minimality problems
- Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
- On the relative complexity of approximate counting problems
- Some hard families of parameterized counting problems
- Randomized Approximations of Parameterized Counting Problems
- Parameterized Derandomization
- A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
- Balanced hashing, color coding and approximate counting
- Approximate counting with m counters: A detailed analysis
- On counting parameterized matching and packing
- The Parameterized Complexity of Counting Problems
- Weighted counting of \(k\)-matchings is \#W[1]-hard
- Counting problems in parameterized complexity
- Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
- Approximate counting and NP search problems
- Approximate Counting of k-Paths: Deterministic and in Polynomial Space
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- A fixed-parameter perspective on \#BIS
- On the parameterized complexity of approximate counting
- Counting matchings of size \(k\) is \#W[1]-hard
- Approximate Counting with Deterministic Guarantees for Affinity Computation
- Algorithms and Data Structures
- The \(k\)-distinct language: parameterized automata constructions
- Counting Small Induced Subgraphs with Hereditary Properties
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- Parameterized Counting and Cayley Graph Expanders
- Vertex cover problem parameterized above and below tight bounds
- The complexity of pattern counting in directed graphs, parameterised by the outdegree
- Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- Counting temporal paths
- Approximately counting answers to conjunctive queries with disequalities and negations
- Testing network correlation efficiently via counting trees
- The complexity of counting homomorphisms seen from the other side
- Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
- Deterministically counting k-paths and trees parameterized by treewidth in single-exponential time
- Compactors for parameterized counting problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The parameterized complexity of probability amplification
This page was built for publication: Approximation algorithms for some parameterized counting problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4427867)
