Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
DOI10.1137/1.9781611974331.CH113zbMATH Open1409.68126OpenAlexW4237554979MaRDI QIDQ4575697FDOQ4575697
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
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)
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)
Cited In (8)
- Compactors for parameterized counting problems
- Title not available (Why is that?)
- Grundy Distinguishes Treewidth from Pathwidth
- Title not available (Why is that?)
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- Title not available (Why is that?)
- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
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)
