Programming Research Group Research Report RR-03-13

Andrei A. Bulatov and Victor Dalmau

July 2003, 37pp.

Abstract

The Counting Constraint Satisfaction Problem (#CSP) over a finite domain can be expressed as follows: given a first-order formula consisting of a conjunction of predicates, determine the number of satisfying assignments to the formula. It provides a general framework for numerous counting combinatorial problems including counting satisfying assignments to a propositional formula, graph homomorphisms, graph reliability and many others. #CSP can be parametrized by the set of allowed constraint predicates.

In this paper we start a systematic study of subclasses of #CSP restricted in this way. The ultimate goal of this investigation is to distinguish those restricted subclasses of #CSP which are solvable in polynomial time from those which are not. We show that the complexity of any restricted #CSP class on a finite domain can be deduced from the properties of polymorphisms of the allowed constraints, similar to that for the decision constraint satisfaction problem. Then we prove that if a subclass of the #CSP is solvable in polynomial time, then constraints allowed by the class satisfy some very restrictive condition: it has to have a Mal'tsev polymorphism, that is a ternary operation m(x,y,z) such that m(x,y,y)=m(y,y,x)=x. This condition uniformly explains all existing complexity results for particular cases of #CSP, and allows us to obtain new results and to conjecture a criterion distinguishing counting constraint satisfaction problems solvable in polynomial time. We also apply these results to obtain a dichotomy theorem for the complexity of #CSP with a 3-element domain and give a new simpler proofs of the dichotomy results for the problem of counting graph homomorphisms.