Min CSP on Four Elements: Moving Beyond Submodularity
This is joint work with Peter Jonsson and Fredrik Kuivinen. We present a computational complexity classification of Min CSP (or, equivalently Max CSP) for constraint languages over a four-element domain. The result shows that every such problem is either tractable or NP-complete. Similar classifications are known for the two- and three-element domain cases. To prove our result, we introduce a new class of tractable problems based on combining submodular- and bisubmodular function minimisation. We further establish some basic techniques which allow us to obtain the result without relying on computer-assisted case analyses (which were heavily used in the classification of Max CSP on a three-element domain). Our result shows, for the first time, that submodularity is not the only source of traceability for Min CSP.
