Counting Matchings of Size k Is $\sharp$ W[1]-Hard
From MaRDI portal
Publication:5326574
DOI10.1007/978-3-642-39206-1_30zbMath1336.68096MaRDI 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
05C30: Enumeration in graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)