TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 09441

The Constraint Satisfaction Problem: Complexity and Approximability

( Oct 25 – Oct 30, 2009 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/09441

Organizers




Schedule

Summary

The constraint satisfaction problem, or CSP in short, provides a unifying framework in which it is possible to express, in a natural way, a wide variety of algorithmic problems, including propositional satisfiability, graph colorability, and systems of equations. This framework has been extensively used in theoretical computer science, both as a mathematical object with rich structure that deserves investigation in its own right and as a versatile vehicle for algorithmic techniques. The constraint satisfaction problem was studied in the 1970s by researchers in artificial intelligence working on computer vision. From the 1980s on, it has been studied in database theory under the guise of the conjunctive query containment problem, as well as in combinatorics and finite model theory under the name of the homomorphism problem for graphs and for arbitrary relational structures. Only in the last decade, however, it was realized that all these problems are different faces of the same fundamental problem. Consequently, it is important to analyze and pinpoint the the computational complexity of certain algorithmic tasks related to constraint satisfaction.

Constraint satisfaction has been ubiquitous in computational complexity theory from its early beginnings. For example, as mentioned earlier, propositional satisfiability and graph colorability, two of the very first problems shown to be NP-complete, are particular cases of CSP. Since the constraint satisfaction problem is computationally hard in its full generality, researchers have toiled for the past thirty years to discover tractable cases of CSP and have strived, and continue to strive, to delineate the boundary between tractability and intractability for this problem. During the past two decades, an impressive array of diverse methods from several different mathematical fields, including universal algebra, logic, and graph theory, have been used to analyze both the computational complexity of algorithmic tasks related to the constraint satisfaction problem and the applicability/limitations of algorithmic techniques. Although significant progress has been made on several fronts, some of the central questions remain open to date. The most prominent among them is the Dichotomy Conjecture for the complexity of the decision version of CSP posed by Feder and Vardi in 1993.

The seminar brought together forty researchers from different highly advanced areas of constraint satisfaction and with complementary expertise (logical, algebraic, combinatorial, probabilistic aspects). The list of participants contained both senior and junior researchers and a small number of advanced graduate students.

The seminar included two substantial tutorials: one on the classification of the complexity of constraint languages via methods of logic and universal algebra (given by A. Krokhin from Durham U, UK), and the other on the approximability of CSP (given by V. Guruswami from Carnegie Mellon U, US). The recent breakthroughs on the topic of the seminar were presented by their respective authors in one-hour lectures, as follows:

  1. P. Austrin (New York U, US), Approximation Resistance
  2. A. Bulatov (Simon Fraser U, CA), Counting CSP
  3. M. Kozik (Jagiellonian U, PL), CSPs of Bounded Width
  4. D. Marx (Tel Aviv U, IL), Structural Complexity of CSPs: The Role of Treewidth and Its Generalisations
  5. P. Raghavendra (U Washington, US), Complexity of Approximating CSPs.

Other participants presented, in 19 further 30-minute talks, their re- cent results on a number of important questions concerning the topic of the seminar.

The seminar was essentially the first meeting of researchers from both the constraint satisfaction community and the complexity of approximation community. The general consensus was that both communities have learned a lot about the goals, methods and techniques of one another, and that there is a potential of a systematic interaction that may cross- fertilize the areas and open new research directions, so it is worthwhile to maintain communication and to arrange further joint meetings.


Participants
  • Albert Atserias (UPC - Barcelona, ES) [dblp]
  • Per Austrin (KTH Royal Institute of Technology, SE) [dblp]
  • Manuel Bodirsky (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
  • Catarina Alexandra Carvalho (University of Lisboa, PT) [dblp]
  • Hubie Chen (UPF - Barcelona, ES) [dblp]
  • David Cohen (Royal Holloway University of London, GB) [dblp]
  • Nadia Creignou (University of Marseille, FR) [dblp]
  • Victor Dalmau (UPF - Barcelona, ES) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Laszlo Egri (McGill University - Montreal, CA) [dblp]
  • John Faben (Queen Mary University of London, GB)
  • Leslie Ann Goldberg (University of Liverpool, GB) [dblp]
  • Venkatesan Guruswami (Carnegie Mellon University, US) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Miki Hermann (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
  • Peter Jonsson (Linköping University, SE) [dblp]
  • Lefteris M. Kirousis (RACTI - Rion, GR) [dblp]
  • Phokion G. Kolaitis (IBM Almaden Center, US) [dblp]
  • Swastik Kopparty (MIT - Cambridge, US) [dblp]
  • Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
  • Andrei Krokhin (Durham University, GB) [dblp]
  • Fredrik Kuivinen (Linköping University, SE)
  • Florent R. Madelaine (Clermont University, FR) [dblp]
  • Elitza Maneva (UPC - Barcelona, ES) [dblp]
  • Petar Markovic (University of Novi Sad, RS)
  • Barnaby Martin (University Paris-Diderot, FR) [dblp]
  • Dániel Marx (Tel Aviv University, IL) [dblp]
  • Gustav Nordh (Linköping University, SE)
  • Prasad Raghavendra (University of Washington - Seattle, US) [dblp]
  • Iain A. Stewart (Durham University, GB) [dblp]
  • Rustem Takhanov (Linköping University, SE)
  • Pascal Tesson (Laval University - Quebec, CA)
  • Marc Thurley (HU Berlin, DE)
  • Matt Valeriote (McMaster University - Hamilton, CA) [dblp]
  • Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
  • Magnus Wahlström (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Ross Willard (University of Waterloo, CA) [dblp]
  • Stanislav Živný (University of Oxford, GB) [dblp]

Related Seminars
  • Dagstuhl Seminar 06401: Complexity of Constraints (2006-10-01 - 2006-10-06) (Details)
  • Dagstuhl Seminar 12451: The Constraint Satisfaction Problem: Complexity and Approximability (2012-11-04 - 2012-11-09) (Details)
  • Dagstuhl Seminar 15301: The Constraint Satisfaction Problem: Complexity and Approximability (2015-07-19 - 2015-07-24) (Details)
  • Dagstuhl Seminar 18231: The Constraint Satisfaction Problem: Complexity and Approximability (2018-06-03 - 2018-06-08) (Details)
  • Dagstuhl Seminar 22201: The Constraint Satisfaction Problem: Complexity and Approximability (2022-05-15 - 2022-05-20) (Details)
  • Dagstuhl Seminar 25211: The Constraint Satisfaction Problem: Complexity and Approximability (2025-05-18 - 2025-05-23) (Details)

Classification
  • data structures
  • algorithms
  • complexity

Keywords
  • constraint satisfaction problem (CSP)
  • satisfiability
  • computational complexity
  • CSP dichotomy conjecture
  • hardness of approximation
  • unique games conjecture
  • random CSP
  • universal algebra
  • logic.