Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

DOI10.1137/1.9781611974331.ch113zbMath1409.68126OpenAlexW4237554979MaRDI QIDQ4575697

Radu Curticapean, Dániel Marx

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch113

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Compactors for parameterized counting problems ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus