Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-034 | 18th April 2002 00:00

Mal'tsev constraints are tractable

RSS-Feed




TR02-034
Authors: Andrei Bulatov
Publication: 18th June 2002 16:43
Downloads: 1439
Keywords: 


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.



ISSN 1433-8092 | Imprint