Counting combinatorial problems and Mal'tsev algebras
by
Andrei A. Bulatov
Oxford University Computing Laboratory, Oxford, UK

Many combinatorial search problems can be expressed as `constraint satisfaction problem' (CSP). In a constraint satisfaction problem the aim is to find an assignment of values to a given set of variables, subject to specified constraints. During the last several years an algebraic approach to the study of CSP has been developed by P.Jeavons and coauthors. The essence of the approach is that it assigns a finite algebra to every subproblem of the CSP so that the complexity of the subproblem depends entirely on the properties of the assigned algebra.

We extend this approach to the Counting Constraint Satisfaction Problem in which the aim is to find the number of solutions rather than recognize their existence. In particular, we show that if a subproblem of the Counting CSP is polynomial time solvable then the corresponding algebra is Mal'tsev.

Date received: March 6, 2003