An Effective Dichotomy for the Counting Constraint Satisfaction Problem
Authors:
- Martin DyerMDMartin Dyer
- David RicherbyDRDavid Richerby
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 42 (3) , 1245-1274
Abstract
Bulatov [Proceedings of the $35$th International Colloquium on Automata, Languages and Programming (Part 1), Lecture Notes in Comput. Sci. 5125, Springer, New York, 2008, pp. 646--661] gave a dichotomy for the counting constraint satisfaction problem \#CSP. A problem from \#CSP is characterized by a constraint language $\Gamma\!$, a fixed, finite set of relations over a finite domain $D$. An instance of the problem uses these relations to constrain an arbitrarily large finite set of variables. 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 [SIAM J. Comput., 36 (2006), pp. 16--27]. 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.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- A Complexity Dichotomy For Hypergraph Partition Functionscomputational complexity, 2010
- The Complexity of Weighted Boolean #CSPSIAM Journal on Computing, 2009
- On counting homomorphisms to directed acyclic graphsJournal of the ACM, 2007
- Towards a dichotomy theorem for the counting constraint satisfaction problemInformation and Computation, 2007
- A Simple Algorithm for Mal'tsev ConstraintsSIAM Journal on Computing, 2006
- A dichotomy theorem for constraint satisfaction problems on a 3-element setJournal of the ACM, 2006
- The complexity of partition functionsTheoretical Computer Science, 2005
- The complexity of counting graph homomorphismsRandom Structures & Algorithms, 2000
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group TheorySIAM Journal on Computing, 1998
- Complexity of Generalized Satisfiability Counting ProblemsInformation and Computation, 1996