The Parameterized Complexity of Counting Problems
From MaRDI portal
Publication:4651498
DOI10.1137/S0097539703427203zbMath1105.68042OpenAlexW2137874581MaRDI QIDQ4651498
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539703427203
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items (71)
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ The complexity of finding optimal subgraphs to represent spatial correlation ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Graph operations and neighborhood polynomials ⋮ Tractable counting of the answers to conjunctive queries ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Answer Counting under Guarded TGDs ⋮ Parameterised counting in logspace ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Parameterized random complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding and counting vertex-colored subtrees ⋮ Faster algorithms for finding and counting subgraphs ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ A Lanczos-like method for non-autonomous linear ordinary differential equations ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Confronting intractability via parameters ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Cycle-maximal triangle-free graphs ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ On Counting Parameterized Matching and Packing ⋮ Counting the number of independent sets in chordal graphs ⋮ Counting linear extensions: parameterizations by treewidth ⋮ Solving \#SAT using vertex covers ⋮ Computing the number of induced copies of a fixed graph in a bounded degree graph ⋮ The parameterized complexity of maximality and minimality problems ⋮ On the complexity of finding and counting solution-free sets of integers ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ The parameterized complexity of probability amplification ⋮ Parameterized approximation of dominating set problems ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tridiagonalization of systems of coupled linear differential equations with variable coefficients by a Lanczos-like method ⋮ On the parameterized complexity of approximate counting ⋮ Parameterized counting of partially injective homomorphisms ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity ⋮ Approximately Counting Embeddings into Random Graphs ⋮ Unnamed Item ⋮ Refining invariants for computing autotopism groups of partial Latin rectangles ⋮ Counting Answers to Existential Questions ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Some Hard Families of Parameterized Counting Problems ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ On counting 3-D matchings of size \(k\) ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting ⋮ Unnamed Item ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Unnamed Item ⋮ Counting short cycles of (c,d)-regular bipartite graphs ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
This page was built for publication: The Parameterized Complexity of Counting Problems
