Combinatorial problems raised from 2-semilattices

Journal article

The Constraint Satisfaction Problem (CSP) provides a general framework for many combinatorial problems. In [A.A. Bulatov, A.A. Krokhin, P.G. Jeavons, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (3) (2005) 720–742; P.G. Jeavons, On the algebraic structure of combinatorial problems, Theoret. Comput. Sci. 200 (1998) 185–204] and then in [A.A. Bulatov, P.G. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001, Technische Universität Dresden, Dresden, Germany, 2001], a new approach to the study of the CSP has been developed which uses properties of universal algebras assigned to certain subclasses of the CSP such that the time complexity and other properties of subclasses can be derived from the properties of the assigned algebras. In this paper we briefly survey this approach, and then prove that problem classes corresponding to finite 2-semilattices, that is groupoids satisfying the identities xx=x, xy=yx, x(xy)=(xx)y, can be solved in polynomial time. Making use of this result we classify finite conservative groupoids, and 4-element algebras with minimal clone of term operations with respect to the complexity of the corresponding CSP-class.

Authors: Bulatov, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Algebra
• Volume: 298
• Issue: 2
• Pages: 321-339
• Publication date: 2006-04-01
• Edition: Publisher's version
• DOI: 10.1016/j.jalgebra.2004.07.044
• ISSN: 0021-8693
• Language: English
• Keywords: constraint satisfaction problem; 2-semilattice; groupoid; minimal clone
• Subjects: Mathematics