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

(19)

• Compactors for parameterized counting problems
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
• Grundy Distinguishes Treewidth from Pathwidth
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
• Towards exact structural thresholds for parameterized complexity
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• Counting problems in parameterized complexity
• Almost tight lower bounds for hard cutting problems in embedded graphs
• Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• Grundy distinguishes treewidth from pathwidth
• Hitting meets packing: how hard can it be?
• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• 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)
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results

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)