From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
From MaRDI portal
Publication:1934313
DOI10.1007/s00453-012-9626-6zbMath1255.68079MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Unnamed Item, Unnamed Item, Counting Small Induced Subgraphs Satisfying Monotone Properties, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, On the Complexity of Holant Problems, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, Complexity classification of the eight-vertex model, A dichotomy for real weighted Holant problems, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Computing and estimating the volume of the solution space of SMT(LA) constraints, Holographic algorithms beyond matchgates, 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, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
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
