Table of Contents
Algorithms and Complexity of Constraint Satisfaction Problems (24h, 3 ECTS)Responsible : Miki Hermann (LIX, École Polytechnique) Teachers for 20122013 :
Motivation and Goals of the CoursConstraint Satisfaction Problems (CSPs, problèmes de satisfaction de contraintes) appeared in the middle of 1970s, when researchers recognised their importance after Montanari's publication. This research domain knew a boom starting at the end of 1990s. The popularity of CSPs is due to the fact that this formalism allows to address very diverse algorithmic problems in the same framework. They also allow to develop algorithms that are universally applicable in many areas of computing. CSPs find applications in almost all parts of computer science, such as constraint programming, complexity theory, bioinformatics, theory and applications of databases (especially query optimization and data integration), software verification, operations research, reasoning in nonmonotonic logic, artificial intelligence, to name only a few. The research in CSP combines methods from combinatorics and graph theory, model theory, universal algebra, and complexity theory. Students, after completing this course, will have an overview of CSP, their importance, their applications, the underlying algorithms and complexity. Plan of the CourseThe first part consists of 8 sessions, each for 1.5 hours. The second part of 8 sessions, each for 1.5 hours. The first part of the course will be devoted to Boolean CSPs and their complexity, based on the articles and monographs (Hell et Nesetril 2004), (Creignou, Khanna et Sudan 2001) and (Böhler et al. 2003), (Böhler et al. 2004), (Jeavons, Cohen et Gyssens 1997), (Creignou et Hermann 1996). We start with a brief motivation for the use of CSPs with examples including the frequency assignment problem or correction of an Intel processor, thus arriving to explain the necessity and usefulness of the course. We introduce the concepts of relational structures, constraints, and satisfaction, which leads us to the main definition of the CSP. We present some concrete examples of CSPs, such as the alldifferent and 3coloring problem. We explain how to parameterize CSPs by means of a constraint language S consisting of a set of relations – according to this parameter the CSP can be polynomialtime tractable or NPcomplete. We will also briefly address the problems of counting, approximation, unique satisfiability or quantified satisfiability, equivalence and isomorphism, maximum satisfiability, and problems related to databases, all in relation with CSPs. The second part of the course applies the concepts and techniques of the first part to CSPs over infinite domains. In particular, we study computational problems in spatial and temporal reasoning, phylogenetic reconstruction, and graph theory. Our focus will be on polynomialtime solvable CSPs, and the frontiers of tractability. Another central topic are local consistency techniques in constraint processing. Schedule of LecturesAccording to the schedule of MPRI. More information about this course and its schedule is available on the web pages Miki Hermann or Miki Hermann and Manuel Bodirsky . Teaching LangueMiki Hermann has prepared the course in French, but he can give the lectures in English by request of nonfrancophone students. Manuel Bodirsky will be giving his lectures in English. The exam subject will be written both in French and English. The students are authorized to write the exam in French or in English, according to their own choice. Support Material for the Course :The slides of the course will be available progressively on the web pages MPRI C2311 MH or MPRI C2311 MH and MPRI C2311 MB. PrerequisitesBasic knowledge in complexity and in algorithmics is required. Related CoursesOptimisation 2241, Constraint programming 2351 Bibliography
Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. SIGACT News, Complexity Theory Column 42, 34(4):3852, 2003.
Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News, Complexity Theory Column 43, 35(1):2235, 2004.
Bases for Boolean coclones. Information Processing Letters, 96(2):5966, 2005.
A Rendezvous of Logic, Complexity, and Algebra. ACM Computing Surveys, 42(1): 2009.
Complexity of generalized satisfiability counting problems. Information and Computation, 125(1):112, 1996.
Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (PA), 2001.
Graphs and Homomorphisms. Oxford University Press, 2004.
Closure properties of constraints. Journal of the ACM, 44(4):527548, 1997. ExamsMidterm exam is scheduled on 4 December 2012, final exam is scheduled on 12 March 2013. Teaching Staff
