Towards a dichotomy theorem for the counting constraint satisfaction problem

DOI10.1016/j.ic.2006.09.005zbMath1115.68141OpenAlexW2131358503MaRDI QIDQ879594

Andrei A. Bulatov, Victor Dalmau

Publication date: 14 May 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10230/36327

zbMATH Keywords

complexityconstraint satisfaction problemcounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (36)

Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Counting \(4 \times 4\) matrix partitions of graphs ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Testing list \(H\)-homomorphisms ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Holographic reduction, interpolation and hardness ⋮ Counting List Matrix Partitions of Graphs ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ A new line of attack on the dichotomy conjecture ⋮ Complexity classification of the eight-vertex model ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Enumerating homomorphisms ⋮ The complexity of weighted and unweighted \(\#\)CSP ⋮ Holographic algorithms beyond matchgates ⋮ The complexity of problems for quantified constraints ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Counting Constraint Satisfaction Problems. ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ An approximation trichotomy for Boolean \#CSP ⋮ The complexity of counting homomorphisms seen from the other side ⋮ On the Complexity of Reconstructing H-free Graphs from Their Star Systems ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ On algebras with many symmetric operations ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ The complexity of partition functions ⋮ A dichotomy for real weighted Holant problems ⋮ \(H\)-coloring dichotomy revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Graph homomorphisms and phase transitions
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Conjunctive-query containment and constraint satisfaction
• Counting \(H-\)colorings of partial \(k-\)trees
• The restrictive \(H\)-coloring problem
• A new tractable class of constraint satisfaction problems
• Hereditarily hard \(H\)-colouring problems
• Networks of constraints: Fundamental properties and applications to picture processing
• Complexity of generalized satisfiability counting problems
• On \(n\)-permutable congruences
• The complexity of partition functions
• Dempster's rule of combination is {\#}P-complete
• On the hardness of approximate reasoning
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Hard Enumeration Problems in Geometry and Combinatorics
• The Complexity of Enumeration and Reliability Problems
• The structure of finite algebras
• The Complexity of Planar Counting Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On Approximately Counting Colorings of Small Degree Graphs
• Non-uniqueness of measures of maximal entropy for subshifts of finite type
• Closure properties of constraints
• Computing and Combinatorics
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• Duality and Polynomial Testing of Tree Homomorphisms
• When is the evaluation of conjunctive queries tractable?
• The complexity of satisfiability problems
• Automata, Languages and Programming
• Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Towards a dichotomy theorem for the counting constraint satisfaction problem