## Paper: Generalized Majority-Minority Operations are Tractable (at LICS 2005)

**Víctor Dalmau**

### Abstract

Let A be a finite set and let ? : A k? A with k being ? 3 be a k-ary operation on A. We say that ? is a generalized majority-minority (GMM) operation if for all a,b ? A we have that ? (x,y,..,y) = ? (y,x,..,y) = . . . = ? (y,y,..,x) = y for all x,y ? {a,b} or ? (x,y,..,y) = ? (y,y,..,x) = x for x,y ? {a,b} Near-unanimity and Mal’tsev operations are particular instances of GMM operations. We prove that every CSP instance where all constraint relations are invariant under a (fixed) GMM operation is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.

### BibTeX

@InProceedings{Dalmau-GeneralizedMajority, author = {Víctor Dalmau}, title = {Generalized Majority-Minority Operations are Tractable}, booktitle = {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)}, year = {2005}, month = {June}, pages = {438--447}, location = {Chicago, USA}, publisher = {IEEE Computer Society Press} }