Dagstuhl Seminar 18231
The Constraint Satisfaction Problem: Complexity and Approximability
( Jun 03 – Jun 08, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18231
Organizers
- Martin Grohe (RWTH Aachen, DE)
- Venkatesan Guruswami (Carnegie Mellon University - Pittsburgh, US)
- Dániel Marx (Hungarian Academy of Sciences - Budapest, HU)
- Stanislav Živný (University of Oxford, GB)
Contact
- Shida Kunz (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Schedule
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 decade, 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 logical approaches to CSPs. The participants will also explore the interactions between these topics.
Creative Commons BY 3.0 DE
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný
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 colourability, and systems of equations. The CSP framework originated 30-35 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 the 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, or (b) 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 counting assignments or involve soft 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, 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 universal 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. In the last decade, research activity in this area has significantly intensified and hugely impressive progress was made.
The recent flurry of activity on the topic of the seminar is witnessed by four previous Dagstuhl seminars, titled "Complexity of constraints" (06401) and "The CSP: complexity and approximability" (09441, 12541, 15301), that were held in 2006, 2009, 2012, and 2015 respectively. This seminar was a follow-up to the 2009, 2012, and 2015 seminars. Indeed, the exchange of ideas at the 2009, 2012, and 2015 seminars has led to ambitious new research projects and to establishing regular communication channels. There is clearly the potential for further systematic interaction that will keep on cross-fertilising the areas and opening new research directions. The 2018 seminar brought together 47 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 24 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 a multitude of impressive results reported during the seminar and 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 another seminar focusing 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 problems (say, between P and NP-complete, assuming P =/ NP), 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 the 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 was 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 the 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), culminating in two independent proofs of the general conjecture announced in 2017 by Bulatov and Zhuk.
- Bulatov and Zhuk gave detailed talks on the main insights into their proofs.
- Kolmogorov described an algorithm for Boolean CSPs under the restriction that every variable appears in exactly two constraints and all constraints are even Delta-matroids.
The valued CSP (VCSP) is a significant generalisation of the CSP that involves both feasibility and optimisation aspects. While the computational complexity of finite-domain VCSPs is by now well understood, the infinite-domain VCSPs are fairly unexplored.
- Viola gave a talk on submodular VCSPs on infinite domains.
- Kazda presented his results on the structure of weighted clones, which are intimately related to the computational complexity of VCSPs.
Approximability of CSPs. The use of approximation algorithms is one of the most fruitful approaches to coping with NP-hardness. Hard optimisation problems, however, exhibit diverse behavior with respect to approximability, making it an exciting research area that is by now well-developed but far from fully understood.
An emerging topic bridging the complexity of the CSP with approximation aspects is promise constraint satisfaction (PCSP). The PCSP is a generalization of the CSP in which the constraints come in pairs of "stricter" and "weaker" versions. In a PCSP instance, the task is to find an assignment satisfying the weaker constraints under the promise that there is an assignment satisfying the strict constraints.
- Brakensiek gave an introductory talk to this exciting research direction and also presented a dichotomy classification for symmetric Boolean PCSPs.
- Oprsal explained the very recently introduced algebraic approach to the computational complexity of PCSPs.
- Barto presented his results on PCSPs and cyclic operations.
Many approximation algorithms for CSPs are based on convex relaxations.
- Berkholz gave an overview on relaxations for Boolean CSPs based on algebraic methods.
- Schramm explained the power of semidefinite programming relaxations for random CSPs.
- Tulsiani presented results on the limits of linear programming relaxations for CSPs.
- Makarychev showed how to obtain an integrality gap for the Calinescu-Karloff-Rabani linear programming relaxation of the Multiway-Cut problem.
- Austrin established the currently best known inapproximability result for Min UnCut, which is a special Boolean CSP.
Some of the most exciting developments in approximability in the last decade revolve around the unique games conjecture, or UGC, of Khot (2002). This bold conjecture asserts that, for CSPs with a certain constraint language over a large enough domain, it is NP-hard to distinguish almost satisfiable instances from those where only a small fraction of constraints can be satisfied. This conjecture is known to imply tight inapproximability results for many classical optimisation problems. Moreover, if the UGC is true, then, as shown by Raghavendra in 2008, a simple algorithm based on semidefinite programming provides the best possible approximation for all CSPs (though the exact quality of this approximation is unknown).
- Moshkovitz presented recent developments on the so-called 2-to-2 PCP theorem, which covers important special cases of the UGC.
Logic and the complexity of CSPs. Logic has been used in two distinct ways in the study of the CSP. One of them, starting from earlier work of Kolaitis and Vardi, is descriptive complexity, where one tries to classify CSPs as classes of instances with respect to definability in a given logic. The other way is to use logic to specify CSP instances, which can be done very naturally. The latter direction leads to generalisations such as the quantified CSP (QCSP), as well as to the study of CSPs over infinite domains, where important links with the algebraic approach were found.
- Roy presented a dichotomy theorem for the inverse satisfiability problem.
- Bodirsky gave a talk on two methods of reducing infinite-domain CSPs to finite-domain CSPs.
- Pinsker explained recent results on the algebraic approach to infinite-domain CSPs. These results are related to the so-called loop conditions, which were in more detail discussed by Kozik.
- Kompatscher presented a proof of the equivalence of two dichotomy conjectures for infinite-domain CSPs.
- Mottet gave a new proof of the dichotomy for MMSNP and discussed consequences for infinite-domain CSPs.
- Martin described recent results for temporal and spatial problems, which are special cases of infinite-domain CSPs.
Exact exponential complexity of CSPs. The area of parameterised complexity is closely related to the area of exact exponential complexity, in which the goal is to design the most efficient exponential-time algorithms. There has been significant progress on the exact exponential complexity of CSPs.
- Golovnev presented results that give optimal lower bounds on the running time of algorithms for deciding if there is a homomorphism from one graph to another.
- The complexity of counting solutions for CSPs and related problems from statistical physics were presented by Goldberg and Jerrum.
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný
- Isolde Adler (University of Leeds, GB) [dblp]
- Per Austrin (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Libor Barto (Charles University - Prague, CZ) [dblp]
- Christoph Berkholz (HU Berlin, DE) [dblp]
- Manuel Bodirsky (TU Dresden, DE) [dblp]
- Joshua Brakensiek (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Clement Carbonnel (University of Oxford, GB) [dblp]
- Hubie Chen (Universidad del País Vasco - Donostia, ES) [dblp]
- Victor Dalmau (UPF - Barcelona, ES) [dblp]
- Peter Fulla (University of Oxford, GB) [dblp]
- Leslie Ann Goldberg (University of Oxford, GB) [dblp]
- Alexander Golovnev (Yahoo! Research - New York, US) [dblp]
- Martin Grohe (RWTH Aachen, DE) [dblp]
- Venkatesan Guruswami (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Johan Hastad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
- Peter Jonsson (Linköping University, SE) [dblp]
- Alexandr Kazda (Charles University - Prague, CZ) [dblp]
- Eun Jung Kim (University Paris-Dauphine, FR) [dblp]
- Vladimir Kolmogorov (IST Austria - Klosterneuburg, AT) [dblp]
- Michael Kompatscher (Charles University - Prague, CZ) [dblp]
- Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
- Andrei Krokhin (Durham University, GB) [dblp]
- Victor Lagerqvist (TU Dresden, DE) [dblp]
- Euiwoong Lee (New York University, US) [dblp]
- Yury Makarychev (TTIC - Chicago, US) [dblp]
- Barnaby Martin (Durham University, GB) [dblp]
- Dana Moshkovitz (University of Texas - Austin, US) [dblp]
- Antoine Mottet (TU Dresden, DE) [dblp]
- Ryan O'Donnell (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Miroslav Olsak (Charles University - Prague, CZ) [dblp]
- Jakub Opršal (TU Dresden, DE) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michael Pinsker (TU Wien, AT) [dblp]
- Akbar Rafiey (Simon Fraser University - Burnaby, CA) [dblp]
- Miguel Romero (University of Oxford, GB) [dblp]
- Biman Roy (Linköping University, SE) [dblp]
- Tselil Schramm (University of California - Berkeley, 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]
- Caterina Viola (TU Dresden, DE) [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ý (University of Oxford, GB) [dblp]
Related Seminars
- 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 15301: The Constraint Satisfaction Problem: Complexity and Approximability (2015-07-19 - 2015-07-24) (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)
- computational complexity
- CSP dichotomy conjecture
- hardness of approximation
- unique games conjecture
- parameterized complexity
- descriptive complexity
- universal algebra
- logic
- semidefinite programming
