Logic in Computer Science (LICS 2005)

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}
  }