Generalized Majority-Minority Operations are Tractable
Ho Weng Kin, Víctor Dalmau · 2006
Let A be a finite set and let /spl phi/ : A/sup k//spl rarr/A with k/spl ges/3 be a k-ary operation on A. We say that /spl phi/ is a generalized majority-minority (GMM) operation if for all a, b /spl isin/ A we have that /spl phi/(x, y,...,y) = /spl phi/(y, x,..,y) =...=/spl phi/(y, y,..,x) = y for all x, y /spl isin/ {a, b} or /spl phi/{x, y,..,y) = /spl phi/(y, y,..,x) = x for all x, y /spl isin/ {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.