Johan Thapper (LIX)

An instance of the maximum constraint satisfaction problem (Max CSP) is specified by a set of variables, a domain, and a set of constraints. Each constraint imposes a relation over the domain on a subset of variables. The relations are chosen from a fixed set called the constraint language. The goal is to find an assignment of domain values to the variables that satisfies as many constraints as possible. The question is: Given a fixed constraint language, what is the computational complexity of Max CSP?

Until not long ago, all evidence pointed to, and it was conjectured that

  1. Max CSP is tractable whenever the constraint language is supermodular with respect to a lattice; and
  2. This is essentially the only source of tractability for Max CSP.

I will present recent results showing that (1) is correct and that (2) is false.

The talk is based on joint work with Peter Jonsson, Fredrik Kuivinen, and Stanislav Zivny.