|
|
VOLUME 2, ISSUE 4, PAPER 1
|
Generalized Majority-Minority Operations are Tractable
|
©Victor Dalmau, Universitat Pompeu Fabra
|
Abstract
Generalized majority-minority (GMM) operations are introduced as a
common generalization of near unanimity operations and Mal'tsev
operations on finite sets. We show that every instance of the
constraint satisfaction problem (CSP), 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.
|
Publication date: September 28, 2006
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-2(4:1)2006
Hit Counts: 6268 |
 Creative Commons | |
