From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems

DOI10.1007/s00453-012-9626-6zbMath1255.68079OpenAlexW1660495057MaRDI QIDQ1934313

Sangxia Huang, Pinyan Lu, Jin-Yi Cai

Publication date: 28 January 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9626-6

zbMATH Keywords

dichotomyHolant problemholographic reduction\#CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Computing and estimating the volume of the solution space of SMT(LA) constraints ⋮ A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation ⋮ Complexity classification of the eight-vertex model ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ On the Complexity of Holant Problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ Unnamed Item ⋮ Clifford gates in the Holant framework ⋮ Parameterized counting of partially injective homomorphisms ⋮ Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ A dichotomy for real weighted Holant problems

Cites Work

• Unnamed Item
• A computational proof of complexity of some restricted counting problems
• Holographic algorithms: from art to science
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Holant Problems for Regular Graphs with Complex Edge Functions
• Corrigendum: The complexity of counting graph homomorphisms
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On counting homomorphisms to directed acyclic graphs
• On Counting Homomorphisms to Directed Acyclic Graphs
• The Complexity of Weighted Boolean #CSP
• Tensor Geometry
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Holant problems and counting CSP
• Classification of a Class of Counting Problems Using Holographic Reductions
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Automata, Languages and Programming

This page was built for publication: From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems