Counting Matchings of Size k Is $\sharp$ W[1]-Hard
From MaRDI portal
Publication:5326574
DOI10.1007/978-3-642-39206-1_30zbMath1336.68096OpenAlexW2397172610MaRDI QIDQ5326574
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
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
