Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Algorithms and Complexity of Constraint Satisfaction Problems (24h, 3 ECTS)

Responsible : Miki Hermann (LIX, École Polytechnique)

Teachers for 2012-2013 :

  • Manuel Bodirsky (12h)
  • Miki Hermann (12h)

Motivation and Goals of the Cours

Constraint 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 non-monotonic 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 Course

The 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 all-different and 3-coloring 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 polynomial-time tractable or NP-complete. 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 polynomial-time solvable CSPs, and the frontiers of tractability. Another central topic are local consistency techniques in constraint processing.

Schedule of Lectures

According 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 Langue

Miki Hermann has prepared the course in French, but he can give the lectures in English by request of non-francophone 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 C-2-31-1 MH or MPRI C-2-31-1 MH and MPRI C-2-31-1 MB.

Prerequisites

Basic knowledge in complexity and in algorithmics is required.

Related Courses

Optimisation 2-24-1, Constraint programming 2-35-1

Bibliography

  • E. Böhler, N. Creignou, S. Reith, and H. Vollmer.

Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. SIGACT News, Complexity Theory Column 42, 34(4):38-52, 2003.

  • E. Böhler, N. Creignou, S. Reith, and H. Vollmer.

Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News, Complexity Theory Column 43, 35(1):22-35, 2004.

  • E. Böhler, S. Reith, H. Schnoor, and H. Vollmer.

Bases for Boolean co-clones. Information Processing Letters, 96(2):59-66, 2005.

  • H. Chen.

A Rendezvous of Logic, Complexity, and Algebra. ACM Computing Surveys, 42(1): 2009.

  • N. Creignou and M. Hermann.

Complexity of generalized satisfiability counting problems. Information and Computation, 125(1):1-12, 1996.

  • N. Creignou, S. Khanna, and M. Sudan.

Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (PA), 2001.

  • P. Hell and J. Nesetril.

Graphs and Homomorphisms. Oxford University Press, 2004.

  • P. Jeavons, D. Cohen, and M. Gyssens.

Closure properties of constraints. Journal of the ACM, 44(4):527-548, 1997.

Exams

Mid-term exam is scheduled on 4 December 2012, final exam is scheduled on 12 March 2013.

Teaching Staff

Miki Hermann Chargé de recherche CNRS LIX Ecole Polytechnique
Manuel Bodirsky Chargé de recherche CNRS LIX Ecole Polytechnique
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA