PIMS - SFU Discrete Math Seminar: Andrei Bulatov

Abstract:
The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems. The simplest way to state the problem is: Given relational structures (say, graphs) G and H, decide if there is a homomorphism from G to H. The counting version of the CSP, #CSP, asks for the number of such homomorphisms. In order to represent specific problems, the CSP is often restricted in various ways, in particular by fixing the target structure H. Thus, CSP(H) asks if, for a given structure G, there is a homomorphism from G to H. If H is a graph such a problem is often called H-Coloring. The counting versions #CSP(H), #H-Coloring of these problems are defined accordingly.

In this talk we survey the developments in the study of the complexity of #CSP(H) that eventually led to a complete classification of such problems and their various generalizations.