Counting Matchings of Size k Is $\sharp$ W[1]-Hard

DOI10.1007/978-3-642-39206-1_30zbMath1336.68096OpenAlexW2397172610MaRDI QIDQ5326574

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)

Related Items (20)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Extending the characteristic polynomial for characterization of C\(_{20}\) fullerene congeners ⋮ Parameterized counting of trees, forests and matroid bases ⋮ 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 ⋮ Unnamed Item ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ On Counting Parameterized Matching and Packing ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ Some Hard Families of Parameterized Counting Problems ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

This page was built for publication: Counting Matchings of Size k Is $\sharp$ W[1]-Hard