Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions

DOI10.1016/j.tcs.2012.12.043zbMath1300.05246OpenAlexW2067653823MaRDI QIDQ391089

Jin-Yi Cai, Michael Kowalczyk

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.043

zbMATH Keywords

partition functioncounting complexitydichotomy theoremHolant problemholographic algorithm

Mathematics Subject Classification ID

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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Holant problems for 3-regular graphs with complex edge functions ⋮ On the Complexity of Holant Problems ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures

Cites Work

• Unnamed Item
• Unnamed Item
• A computational proof of complexity of some restricted counting problems
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• On the complexity of H-coloring
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Holant Problems for Regular Graphs with Complex Edge Functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• On counting homomorphisms to directed acyclic graphs
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• The Complexity of Enumeration and Reliability Problems
• Holant problems and counting CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs

This page was built for publication: Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions