An effective dichotomy for the counting constraint satisfaction problem

DOI10.1137/100811258MaRDI QIDQ2848220zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Dyer, David Richerby

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.3879

zbMATH Keywords

complexity dichotomyconstraint satisfaction problemcounting problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Bulatov (2008) gave a dichotomy for the counting constraint satisfaction problem #CSP. A problem from #CSP is characterised by a constraint language, which is a fixed, finite set of relations over a finite domain D. An instance of the problem uses these relations to constrain the variables in a larger set. Bulatov showed that the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or is #P-complete. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations which are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint languages, due to Bulatov and Dalmau (2006). We establish a new criterion for the #CSP dichotomy, which we call strong balance, and we prove that this property is decidable. In fact, we establish membership in NP. Thus, we show that the dichotomy is effective, resolving the most important open question concerning the #CSP dichotomy.

Recommendations

• On the complexity of \#CSP
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• scientific article; zbMATH DE number 5999552
• The complexity of the counting constraint satisfaction problem
• Nonnegative weighted \#CSP: an effective complexity dichotomy

Cited in

(47)

• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• The complexity of counting \(\mathrm{CSP}^d\)
• Zero-freeness and approximation of real Boolean Holant problems
• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Tractability in constraint satisfaction problems: a survey
• The constraint satisfaction problem and universal algebra
• On the complexity of \#CSP
• Counting List Matrix Partitions of Graphs
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• The complexity of Boolean Holant problems with nonnegative weights
• The subpower membership problem for finite algebras with cube terms
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Counting constraint satisfaction problems
• Counting problems in parameterized complexity
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Approximability of the eight-vertex model
• Constant-query testability of assignments to constraint satisfaction problems
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Dichotomy result on 3-regular bipartite non-negative functions
• Bipartite 3-regular counting problems with mixed signs
• Dichotomy result on 3-regular bipartite non-negative functions
• Bipartite 3-regular counting problems with mixed signs
• Approximability of the complementarily symmetric Holant problems on cubic graphs
• Complexity classification of the eight-vertex model
• The computational complexity of Holant problems on 3-regular graphs
• The complexity of counting planar graph homomorphisms of domain size 3
• Restricted Holant dichotomy on domains 3 and 4
• Restricted Holant dichotomy on domain sizes 3 and 4
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• From holant to quantum entanglement and back
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• A characterization of efficiently compilable constraint languages
• A combinatorial view of Holant problems on higher domains
• Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
• Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
• Bounded degree nonnegative counting CSP
• On the complexity of \#CSP\(^d\)
• Symmetries and complexity (invited talk)
• On counting (quantum-)graph homomorphisms in finite fields of prime order
• Title not available (Why is no real title available?)
• The complexity of approximating conservative counting CSPs
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits

This page was built for publication: An effective dichotomy for the counting constraint satisfaction problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848220)