Approximate graph colouring and other promise CSPs

It is well-known that finding a 3-colouring of a given graph that is promised to be 3-colourable is NP-complete. One might be interested in a relaxed version of this problem, e.g. finding a colouring of a 3-colourable graph that uses k colours for some fixed k > 3. This falls into a more general scope of so-called promise constraint satisfaction problem (PCSP). A template of a PCSP is a pair of relational structures A and B (e.g. two graphs) with a homomorphism from A to B, the goal is, given a similar structure that is promised to map to A by a homomorphism, find a homomorphism to B. We will talk about a general theory giving some abstract tools to attack the complexity of PCSPs extending the algebraic approach to the constraint satisfaction problem. This new theory brings closer together the universal algebra in the CSP and some methods from approximation of CSPs. We will also show how can be this applied to provide some new hardness of the aforementioned approximate graph colouring.

This is a joint work with Jakub Bulín, Andrei Krokhin, and others.