Counting matchings of size k is \#W[1]-hard

DOI10.1007/978-3-642-39206-1_30MaRDI QIDQ5326574zbMATH OpenOpenAlexFDO

Authors Radu Curticapean

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39206-1_30

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Weighted counting of \(k\)-matchings is \#W[1]-hard
• On Counting Parameterized Matching and Packing
• scientific article; zbMATH DE number 1979521
• Some hard families of parameterized counting problems
• The Parameterized Complexity of Counting Problems

Cited in

(28)

• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Extending the characteristic polynomial for characterization of C\(_{20}\) fullerene congeners
• Randomised enumeration of small witnesses using a decision oracle
• Parameterized counting of partially injective homomorphisms
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Parameterized counting of trees, forests and matroid bases
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Some hard families of parameterized counting problems
• Counting matchings with k unmatched vertices in planar graphs
• On counting parameterized matching and packing
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• Counting problems in parameterized complexity
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Counting connected subgraphs with maximum-degree-aware sieving
• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Counting independent sets in graphs with bounded bipartite pathwidth
• Parameterised counting in logspace
• 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
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting subgraphs in somewhere dense graphs
• Parameterised counting in logspace
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Parameterised holant problems
• The challenges of unbounded treewidth in parameterised subgraph counting problems

This page was built for publication: Counting matchings of size \(k\) is \#W[1]-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326574)