Min CSP on Four Elements
Johan Thapper, AlCo, LIX, Ecole Polytechnique

We look at a classification of Min CSP (or, equivalently Max CSP) for
constraint languages over a four-element domain. Similar
classifications were previously known for two- and three-element
domains. To prove our result, we introduce a new class of tractable
problems based on a mix of submodularity and bisubmodularity. We
further establish some basic techniques which allow us to obtain the
result without relying on computer-assisted case analyses (which was
previously one of the few methods used, e.g., for the classification
of Min CSP on a three-element domain). A particularly interesting
aspect of our result is that it shows, for the first time, that
submodularity is not the only source of tractability for Min CSP.
This is joint work with Peter Jonsson and Fredrik Kuivinen.