https://www.dagstuhl.de/09441

October 25 – 30 , 2009, Dagstuhl Seminar 09441

The Constraint Satisfaction Problem: Complexity and Approximability

Organizers

Andrei A. Bulatov (Simon Fraser University – Burnaby, CA)
Martin Grohe (HU Berlin, DE)
Phokion G. Kolaitis (IBM Almaden Center, US)
Andrei Krokhin (Durham University, GB)

For support, please contact

Dagstuhl Service Team

Documents

List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]

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.

Dagstuhl Seminar Series

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.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.