A. Krokhin and B. Larose Maximum Constraint Satisfaction on Diamonds (November 18, 2004).
In this paper we study the complexity of the (weighted) maximum constr aint satisfaction problem (Max CSP) over an arbitrary finite domain. In this pro blem, one is given a collection of weighted constraints on overlapping sets of v ariables, and the goal is to find an assignment of values to the variables so as to maximize the total weight of satisfied constraints. Max Cut is a typical exa mple of a Max CSP problem. Max CSP is NP-hard in general; however, some restrict ions on the form of constraints may ensure tractability. Recent results indicate that there is a connection between tractability of such restricted problems and supermodularity of the allowed constraint types with respect to some lattice or dering of the domain. We prove several results confirming this. Diamonds are the smallest lattices in terms of the number of comparabilities, and so are as unor dered as a lattice can possibly be. In the present paper, we study Max CSP on di amond-ordered domains. We show that if all allowed constraints are supermodular with respect to such an ordering then the problem can be solved in polynomial (i n fact, in cubic) time. We also prove a partial converse: if the set of allowed constraints includes a certain small family of binary supermodular constraints o n such a lattice, then the problem is tractable if and only if all of the allowe d constraints are supermodular; otherwise, it is NP-hard.