Dagstuhl-Seminar 15301
The Constraint Satisfaction Problem: Complexity and Approximability
( 19. Jul – 24. Jul, 2015 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/15301
Organisatoren
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA)
- Venkatesan Guruswami (Carnegie Mellon University, US)
- Andrei Krokhin (Durham University, GB)
- Dániel Marx (Hungarian Academy of Sciences - Budapest, HU)
Kontakt
- Dagmar Glaser (für administrative Fragen)
Publikationen
- The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
- The Constraint Satisfaction Problem: Complexity and Approximability. Andrei Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Volume 7. February 21, 2017
Impacts
- Even Delta-Matroids and the Complexity of Planar Boolean CSPs - Kazda, Alexandr; Kolmogorov, Vladimir; Rolinek, Michal - Cornell University : arXiv.org, 2016. - 32 pp..
- Testing Assignments to Constraint Satisfaction Problems : article in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) : pp. 525-534 - Chen, Hubie; Valeriote, Matthew A.; Yoshida, Yuichi - Los Alamitos : IEEE, 2016.
Programm
The main aim of this Dagstuhl Seminar is to bring together leading researchers from all areas of activity in the theory of computation who use the constraint satisfaction paradigm, so that they can communicate state-of-the-art advances, share deep insights, and embark on a systematic interaction that will further develop the synergy between the different areas, generate new research avenues, and lead to fruitful attacks on the open problems in this area.
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g. polynomial-time solvable or non-trivially approximable, fixed-parameter tractable or definable in a weak logic). One of the most striking features of this research direction is the variety of different branches of mathematics (including algebra and logic, combinatorics and graph theory, probability theory and mathematical programming) that are used to achieve deep insights in the study of the CSP, and this seminar will contribute towards further synergy in the area. In the last 7-8 years, research activity in this area has significantly intensified and hugely impressive progress was made, but some of the central questions remain open to date.
The main topics addressed during the seminar will include complexity dichotomies for CSP and related problems, approximability of CSPs, parameterized complexity of CSPs, and counting CSPs. The participants will also explore the interactions between these topics.
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 computational problems dealing with mappings and assignments, including satisfiability, graph colorability, and systems of equations. The CSP framework originated 25-30 years ago independently in artificial intelligence, database theory, and graph theory, under three different guises, and it was realised only in the late 1990s that these are in fact different faces of the same fundamental problem. Nowadays, the CSP is extensively used in theoretical computer science, being a mathematical object with very rich structure that provides an excellent laboratory both for classification methods and for algorithmic techniques, while in AI and more applied areas of computer science this framework is widely regarded as a versatile and efficient way of modelling and solving a variety of real-world problems, such as planning and scheduling, software verification and natural language comprehension, to name just a few. An instance of CSP consists of a set of variables, a set of values for the variables, and a set of constraints that restrict the combinations of values that certain subsets of variables may take. Given such an instance, the possible questions include (a) deciding whether there is an assignment of values to the variables so that every constraint is satisfied, or optimising such assignments in various ways, (b) counting satisfying assignments, exactly or approximately, or (c) finding an assignment satisfying as many constraints as possible. There are many important modifications and extensions of this basic framework, e.g. those that deal with valued or global constraints.
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g. polynomial-time solvable or non-trivially approximable, fixed-parameter tractable or definable in a weak logic). It is only natural that CSPs play a role in many high-profile conjectures in complexity theory, exemplified by the Dichotomy Conjecture of Feder and Vardi and the Unique Games Conjecture of Khot.
The recent flurry of activity on the topic of the seminar is witnessed by three previous Dagstuhl seminars, titled "Complexity of constraints" (06401) and "The CSP: complexity and approximability" (09441, 12541), that were held in 2006, 2009, and 2012 respectively. This seminar was a follow-up to the 2009 and 2012 seminars. Indeed, the exchange of ideas at the 2009 and 2012 seminars has led to new ambitious research projects and to establishing regular communications channels, and there is a clear potential of a further systematic interaction that will keep on cross-fertilizing the areas and opening new research directions. The 2015 seminar brought together forty three researchers from different highly advanced areas of constraint satisfaction and involved many specialists who use universal-algebraic, combinatorial, geometric and probabilistic techniques to study CSP-related algorithmic problems. The participants presented, in 28 talks, their recent results on a number of important questions concerning the topic of the seminar. One particular feature of this seminar is a significant increase in the number of talks involving multiple subareas and approaches within its research direction -- a definite sign of the growing synergy, which is one of the main goals of this series of seminars.
Concluding Remarks and Future Plans. The seminar was well received as witnessed by the high rate of accepted invitations and the great degree of involvement by the participants. Because of the multitude of impressive results reported during the seminar and the active discussions between researchers with different expertise areas, the organisers regard this seminar as a great success. With steadily increasing interactions between such researchers, we foresee a new seminar focussing on the interplay between different approaches to studying the complexity and approximability of the CSP. Finally, the organisers wish to express their gratitude to the Scientific Directors of the Dagstuhl Centre for their support of the seminar.
Description of the Topics of the Seminar
Classical computational complexity of CSPs. Despite the provable existence of intermediate (say, between P and NP-complete, assuming P ne NP) problems, research in computational complexity has produced a widely known informal thesis that "natural problems are almost always complete for standard complexity classes". CSPs have been actively used to support and refine this thesis. More precisely, several restricted forms of CSP have been investigated in depth. One of the main types of restrictions is the constraint language restriction, i.e., a restriction on the available types of constraints. By choosing an appropriate constraint language, one can obtain many well-known computational problems from graph theory, logic, and algebra. The study of the constraint language restriction is driven by the CSP Dichotomy Conjecture of Feder and Vardi which states that, for each fixed constraint language, the corresponding CSP is either in P or NP-complete. There are similar dichotomy conjectures concerning other complexity classes (e.g. L and NL). Recent breakthroughs in the complexity of CSP have been made possible by the introduction of the universal-algebraic approach, which extracts algebraic structure from the constraint language and uses it to analyse problem instances. The above conjectures have algebraic versions which also predict in algebraic terms where the boundary between harder problems and easier problems lies. The algebraic approach has been applied to prove the Dichotomy Conjecture in many important special cases (e.g. Bulatov's dichotomy theorems for 3-valued and conservative CSPs), but the general problem remains open. Barto and Willard described the current state-of-the-art in proving this conjecture, gave insights into the main stumbling blocks (notably, the convoluted ways in which systems of linear equations appear in constraint problems), and outlined avenues of attack on those obstacles. Kozik gave a new simplified algorithm for CSPs solvable by local consistency methods, confirming an earlier conjecture. Brown-Cohen presented new results leading to closer interchange of ideas between algebraic and probabilistic approaches to CSPs.
Valued CSP is a significant generalisation of CSP that involves both feasibility and optimisation aspects. The complexity of language-based restriction for VCSPs was considered in the talks by Kolmogorov, Thapper, and Zivný. Very strong result in this direction were reported, especially the ull description of tractable cases modulo CSP, which closes a sequence of strong and unexpected results on VCSPs obtained during last five years.
The complexity of counting solutions for CSPs, with many results, was investigated by Goldberg, Jerrum, and Richerby.
Along with the constraint language restriction on CSP, the other main type is the structural restriction (i.e. restriction on the immediate interaction between variables in instances). Structural restrictions leading to tractability are well-understood, by results of Grohe and Marx. The so-called "hybrid" tractability in CSP, which is tractability that cannot be attributed to a constraint language restriction or to a structural restriction alone, has not received a great deal of attention yet, and is one of the possible avenues of future work. Rolínek, Scarcello, and Zivný described recent results on hybrid tractability for CSPs and VCSPs, including counting problems.
Approximability of CSPs. The use of approximation algorithms is one of the most fruitful approaches to coping with NP-hardness. Hard optimization problems, however, exhibit different behavior with respect to approximability, making it an exciting, and by now, well-developed but far from fully understood, research area. The CSP has always played an important role in the study of approximability. For example, it is well known that the famous PCP theorem has an equivalent reformulation in terms of inapproximability of a certain CSP; moreover, the recent combinatorial proof of this theorem by Dinur in 2006 deals entirely with CSPs. The first optimal inapproximability results by Hastad in 2001 were about certain CSPs, and they led to the study of a new hardness notion called approximation resistance (which, intuitively, means that a problem cannot be approximated beyond the approximation ratio given by picking an assignment uniformly at random, even on almost satisfiable instances). Many CSPs have been classified as to whether they are approximation resistant but there is not even a reasonable conjecture for a full classification. Lee and Tulsiani presented new results on approximation resistance.
Many approximation algorithms for CSPs are based on the Sum-of-Squares method, Linear Programming and Semidefinite Programming. Recent developments in proving lower bounds for such algorithms were presented by Chan and Steurer.
Improved approximation algorithms for certain infinite-domain CSPs related to correlation clustering were given by K. Makarychev.
New applications of algebraic approach to investigate approximability of CSPs were given by Austrin and Dalmau.
Parameterized complexity of CSPs. A different way to cope with NP-hardness is provided by parameterized complexity, which relaxes the notion of tractability as polynomial-time solvability to allow non-polynomial dependence on certain problem-specific parameters. A whole new set of interesting questions arises if we look at CSPs from this point of view. Most CSP dichotomy questions can be revisited by defining a parameterized version; so far, very little work was done in this direction compared to investigations in classical complexity. A new research direction (often called "parameterizing above the guaranteed bound") led to unexpected positive results for Max r-SAT by Alon et al. in 2010. In this direction, the basic question is to decide the fixed-parameter tractability of the following type of problems: if some easily computable estimate guarantees satisfaction at least E constraints, find an assignment that satisfies at least E+k constraints. Y. Makarychev presented recent results, including approximation issues, in this direction that concern the so-called ordering CSP. Wahlström and Yoshida described how algorithms for this problem, also for VCSP, can be designed when the estimate is given by the Linear Programming relaxation.
Logic and the complexity of CSP. Starting from earlier work by Kolaitis ad Vardi, concepts and techniques from logic have provided unifying explanations for many tractable CSPs. This has led to the pursuit of classifications of CSP with respect to descriptive complexity, i.e. definability in a given logic. Logics considered in this context include first order logic and its extensions, finite-variable logics, the logic programming language Datalog and its fragments. Kazda presented his recent results on the two most important open problems on descriptive complexity of CSPs, where he showed that one of these problems reduces to the other. These results are also related to dichotomy questions for complexity classes L and NL.
The CSP can be recast as the problem of deciding satisfiability of existential conjunctive formulas. Chen described recent results in this direction that also involve counting and parameterised complexity. Natural extension of this framework that also allows universal quantifiers is known as the Quantified CSP (QCSP). New results on the complexity of language-restricted QCSPs were presented by Martin. Zhuk gave a proof of an algebraic result that has direct strong consequences for complexity classification of QCSPs.
Bodirsky and Pinsker presented latest developments in infinite domain CSPs, obtained via a mixture of model-theoretic and algebraic methods.
Ochremiak investigated finite-domain CSPs on infinite instances definable by formulas in first-order logic.
Creative Commons BY 3.0 Unported license
Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx
- Albert Atserias (UPC - Barcelona, ES) [dblp]
- Per Austrin (KTH Royal Institute of Technology, SE) [dblp]
- Libor Barto (Charles University - Prague, CZ) [dblp]
- Manuel Bodirsky (TU Dresden, DE) [dblp]
- Jonah Brown-Cohen (University of California - Berkeley, US) [dblp]
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Catarina Alexandra Carvalho (University of Hertfordshire, GB) [dblp]
- Siu On Chan (The Chinese University of Hong Kong, HK) [dblp]
- Hubie Chen (Universidad del País Vasco - Donostia, ES) [dblp]
- Victor Dalmau (UPF - Barcelona, ES) [dblp]
- Laszlo Egri (Simon Fraser University - Burnaby, CA) [dblp]
- Joanna Fijalkow (University of Warsaw, PL) [dblp]
- Serge Gaspers (UNSW - Sydney, AU) [dblp]
- Leslie Ann Goldberg (University of Oxford, GB) [dblp]
- Venkatesan Guruswami (Carnegie Mellon University, US) [dblp]
- Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
- Peter Jonsson (Linköping University, SE) [dblp]
- Alexandr Kazda (IST Austria - Klosterneuburg, AT) [dblp]
- Vladimir Kolmogorov (IST Austria - Klosterneuburg, AT) [dblp]
- Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
- Andrei Krokhin (Durham University, GB) [dblp]
- Euiwoong Lee (Carnegie Mellon University, US) [dblp]
- Konstantin Makarychev (Microsoft Corporation - Redmond, US) [dblp]
- Yury Makarychev (TTIC - Chicago, US) [dblp]
- Rajsekar Manokaran (Indian Institute of Techology - Madras, IN) [dblp]
- Barnaby Martin (Middlesex University - London, GB) [dblp]
- Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Neeldhara Misra (Indian Institute of Science, IN) [dblp]
- Michael Pinsker (University Paris-Diderot, FR) [dblp]
- David Richerby (Oxford University, GB) [dblp]
- Michal Rolinek (IST Austria - Klosterneuburg, AT) [dblp]
- Francesco Scarcello (University of Calabria, IT) [dblp]
- David Steurer (Cornell University, US) [dblp]
- Stefan Szeider (TU Wien, AT) [dblp]
- Johan Thapper (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Madhur Tulsiani (TTIC - Chicago, US) [dblp]
- Matt Valeriote (McMaster University - Hamilton, CA) [dblp]
- Magnus Wahlström (Royal Holloway University of London, GB) [dblp]
- Ross Willard (University of Waterloo, CA) [dblp]
- Yuichi Yoshida (National Institute of Informatics - Tokyo, JP) [dblp]
- Dmitriy Zhuk (Moscow State University, RU) [dblp]
- Stanislav Živný (Oxford University, GB) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 06401: Complexity of Constraints (2006-10-01 - 2006-10-06) (Details)
- Dagstuhl-Seminar 09441: The Constraint Satisfaction Problem: Complexity and Approximability (2009-10-25 - 2009-10-30) (Details)
- Dagstuhl-Seminar 12451: The Constraint Satisfaction Problem: Complexity and Approximability (2012-11-04 - 2012-11-09) (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)
Klassifikation
- data structures / algorithms / complexity
Schlagworte
- constraint satisfaction problem (CSP)
- computational complexity
- CSP dichotomy conjecture
- hardness of approximation
- unique games conjecture
- descriptive complexity
- counting
- universal algebra
- logic
- parameterized complexity
- decomposition methods
