Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-034 | 18th April 2002 00:00

Mal'tsev constraints are tractable


Authors: Andrei Bulatov
Publication: 18th June 2002 16:43
Downloads: 1544


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.

ISSN 1433-8092 | Imprint