Supermodular Functions and the Complexity of MAX CSP

Abstract

In this paper we study the complexity of the maximum constraint satisfaction problem (Max CSP) over an arbitrary finite domain. An instance of Max CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. We describe for the first time a general approach to the question of classifying the complexity of Max CSP for different types of constraints. This approach is based on establishing a novel connection with the theory of sub- and supermodular functions on finite lattice-ordered sets. Using this connection, we are able to identify large classes of efficiently solvable subproblems of Max CSP arising from certain restrictions on the constraint types. All previously known complexity classification results for Max CSP were restricted to constraints over a 2-valued (Boolean) domain. Here we show that these previous results can be restated using supermodularity, and from this we obtain the first examples of general families of efficiently solvable cases of Max CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean Max CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of Max CSP which are hard even to approximate.