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

Authors:**Ho Weng Kin Victor 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{KinDalmau-GeneralizedMajority, author = {Ho Weng Kin and Victor Dalmau}, title = {Generalized Majority-Minority Operations are Tractable}, booktitle = {Proceedings of the Twentieth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2005}, year = 2005, editor = {Prakash Panangaden}, month = {June}, pages = {438--447}, location = {Chicago, USA}, publisher = {IEEE Computer Society Press} }