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

DOI10.1137/1.9781611974331.CH113MaRDI QIDQ4575697zbMATH OpenOpenAlexFDO

Authors 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

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Known algorithms on graphs of bounded treewidth are probably optimal
• scientific article; zbMATH DE number 7075922
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• scientific article; zbMATH DE number 6783432
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)

Cited in

(8)

• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• Compactors for parameterized counting problems
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• Counting problems in parameterized complexity
• Grundy distinguishes treewidth from pathwidth
• Almost tight lower bounds for hard cutting problems in embedded graphs
• Grundy Distinguishes Treewidth from Pathwidth
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)

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

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