Constraint Satisfaction: Algorithms and Complexity

Instructors: Manuel Bodirsky and Miki Hermann
Dates: 18/09/2012 until 05/03/2013.
Time: Tuesday 17:45 -- 19:15
Classroom: Room 109 in the new building Sophie-Germain.

This is the course website for the second part of the MPRI course 2-31-1 Constraint Satisfaction: Algorithms and Complexity.

The topic of this part of the course are graph homomorphism problems and constraint satisfaction problems with infinite domains, with a particular focus on constraint satisfaction problems that can be solved in polynomial time.

The web-site for the first part of the course can be found here.


Some of the topics of the course are illustrated by slides. The course slides will be available after they have been presented in the lecture. Important: these slides cover only a fraction of the material that is presented in the lecture!


The course script for the present course is available here; the text is still subject to modifications. Comments, bugreports, and questions are welcome.



The students of the MPRI are highly welcome to do their MPRI research project on topics related to this course. Formalities about doing your stage at the MPRI can be found here.