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.

Slides

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 first part of the first lecture was an introduction to graph homomorphisms. For the second part on the arc consistency algorithm, we had the following slides: Arc Consistency
Slides from third lecture on Datalog

Script(s)

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

Work-sheets

Stages

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.