__
TR02-034 | 18th April 2002 00:00
__

#### Mal'tsev constraints are tractable

**Abstract:**
A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of suclasses of the CSP depends only on certain algebraic invariance properties of constraints. The tractability of the problem class raised from a finite group has been proved by Feder and Vardi. In this paper we show that an arbitrary family of constraints invariant with respect to a Mal'tsev operation, that is a ternary operation f(x,y,z) satisfying f(y,y,x)=f(x,y,y)=x for any x,y, gives rise to a tractable problem class. Since every group constraint considered by Feder and Vardi is invariant with respect to a certain Mal'tsev operation, the results of this paper imply the mentioned result of Feder and Vardi.