Dagstuhl Seminar 25211
The Constraint Satisfaction Problem: Complexity and Approximability
( May 18 – May 23, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25211
Organizers
- Manuel Bodirsky (TU Dresden, DE)
- Venkatesan Guruswami (University of California - Berkeley, US)
- Dániel Marx (CISPA - Saarbrücken, DE)
- Stanislav Živný (University of Oxford, GB)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
Schedule
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 over 40 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; e.g., (b) finding an assignment satisfying as many constraints as possible, or (c) finding an assignment that violates as few 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 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 universal algebra and logic, combinatorics and graph theory, probability theory and mathematical programming, and most recently topology) that are used to achieve deep insights in the study of the CSP, and the proposed seminar will contribute towards further synergy in the area.
After about 20 years of intense research activity and hugely impressive progress, the culmination of the algebraic-approach to fixed-template CSPs was the resolution of the Feder-Vardi conjecture independently by Bulatov and Zhuk in 2017. While some fundamental questions (such as a fine-grained understanding of tractable CSPs) remain open, new research directions on generalizations of CSPs started emerging. One such direction is the fixed-template Min-CSP studied with respect to fixed-parameter tractability. Another is the fixed-template promise CSP (PCSP), which is motivated by the goal to better understand the approximability of problems with perfect completeness. PCSPs are a vast generalization of CSPs. A prime and well-known example is the approximate graph coloring problem: distinguish k-colorable graphs from graphs that are not even c-colorable, for some fixed c ≥ k. The main topic of this Dagstuhl Seminar is PCSPs, a highly ambitious research directions with intriguing connections to both old open problems (such the approximate graph coloring problem) and new research directions (such as new algorithms for CSPs) and its connections to gems of computational complexity (such as Håstad’s optimal inapproximability results) and fixed-parameter tractability of Min-CSPs, which has recently seen some remarkable progress.
The recent flurry of activity on the topic of the seminar is witnessed by six previous Dagstuhl Seminars, titled “Complexity of constraints” (06401) and “The CSP: complexity and approximability” (09441, 12541, 15301, 18231, 22201), that were held in 2006, 2009, 2012, 2015, 2018, and 2022, respectively. This seminar was a follow-up to the 2009, 2012, 2015, 2018, and 2022 seminars. Indeed, the exchange of ideas at the 2009, 2012, 2015, 2018, and 2022 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 2025 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 and 2 tutorial series, 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 very high rate of accepted invitations (many more researchers would have liked to participate, but we were unable to accommodate them) 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
Following the two independent proofs of the finite-domain CSP dichotomy in 2017 by Bulatov and Zhuk, the research in the area of constraint satisfaction problems focuses on various generalizations of the CSP framework and on uniformizing the approaches to these variants of CSPs. We list the concrete topics of the talks in the seminar below.
Uniform algorithms for finite-domain CSPs
On the topic of understanding better the polynomial-time algorithms for finite-domain CSPs with the hope of getting a uniform algorithm, Dmitriy Zhuk gave an overview talk. He discussed the algorithms for finite-domain CSPs arising from the combination of consistency checking with basic linear programming and affine integer programming, and their singleton variants. He also provided polymorphism conditions for these algorithms to be correct, some of which were not known before.
Infinite-domain CSPs
One of the most natural and intensely studied generalizations of finite-domain CSPs are CSPs with infinite-domain ω-categorical templates. The workshop contained a 2-hour tutorial on such CSPs given by Antoine Mottet.
- In the first part, Mottet presented a template-free approach, showing the similarity between the finite- and infinite-domain CSPs.
- In the second part, he outlined more recent results in the area, in particular the theory of smooth approximations and the connections of infinite-domain CSPs to promise CSPs.
There were 5 contributed talks on recent results in the area of infinite-domain CSPs and related topics.
- Jakub Rydval talked about fundamental questions in infinite-domain constraint satisfaction such as the structural assumptions that can be imposed on the templates in the scope of the Bodirsky-Pinsker conjecture.
- Michał Wrona gave a talk about the complexity of infinite-domain CSPs with bounded strict width in the scope of Bodirsky-Pinsker conjecture.
- Johanna Brunar presented a result on pseudo loops in smooth digraphs.
- Michael Pinsker talked about a necessary polymorphism condition for tractability of CSPs that applies to a large class of finite and ω-categorical templates.
- Maximilian Hadek gave a talk about the connection between König’s tree lemma and Ramsey’s theorem, two important tools for infinite-domain CSPs.
Promise CSPs
Following the trend of the previous workshops, the topic of promise CSPs, which can be viewed as a framework for qualitative approximation in CSPs, was addressed in 3 contributed talks and touched in several more talks.
- Andrei Krokhin presented a proof that PCSP(LO2, LO3) is NP-hard.
- Santiago Guzmán Pro presented his result showing that if the tractability of a finite-template PCSP is explained by a GMSNP sandwich, then it is also explained by a finite sandwich.
- Per Austrin introduced the concept of usefulness for PCSPs, focusing on Boolean PCSPs.
Topological methods for CSPs and PCSPs
Continuing the newly emerging topological approach to classifying complexity of CSPs and PCSPs, there were 2 contributed talks concerning this topic.
- Jakub Opršal gave an introduction to homomorphism complexes and their use in classifying the complexity of CSPs.
- Uli Wagner presented a topological proof that it is NP-hard to distinguish between graphs that are G-colorable and graphs that are not even 4-colorable, where G is any non-bipartite, 4-colorable graph.
Approximability of CSPs
Another prominent topic of the seminar is the quantitative approximability of CSPs, sometimes combined with the setting of promise CSPs to obtain, in some sense, both quantitative and qualitative approximation results. The seminar started with a 3-hour tutorial given by Amey Bhangale.
- In the first part, he presented approximation algorithms and known results on hardness of approximation.
- The second part of the tutorial was focused on Raghavendra’s characterization of the approximability of almost satisfiable Max-CSPs.
- In the third part, he discussed the recent work on the approximability of satisfiable CSPs including the hybrid algorithm that combines SDP rounding and Gaussian elimination algorithms.
There were 8 contributed talks devoted to this topic:
- Silvia Butti presented a result on inapproximability of promise equations over finite groups.
- Libor Barto talked about the framework of valued PCSPs and reduction between them based on the minor condition problem.
- Konstantin Makarychev gave a talk on approximability of phylogenetic CSPs.
- George Osipov presented results on optimal approximation factors for Boolean MinCSPs.
- Euiwoong Lee presented results on approximability of MinCSPs on complete instances.
- Tamio-Vesa Nakajima introduced a new approximation framework called maxPCSPs and presented some complexity results for such problems.
- Santhoshini Velusamy talked about approximability of constraint satisfaction problems in the streaming model.
- Anuj Dawar gave a talk about undefinability of approximation in the sense that hardness is captured by undefinability in FPC.
Other variants of CSPs
There were 3 contributed talks concerning other variants of CSPs than those mentioned above.
- Yury Makarychev presented results on algorithms for CSPs with ML oracle advice.
- Barnaby Martin talked about about a new concept of restricted CSPs on digraphs and a connection to CSPs of digraphs with a restricted class of instances.
- Žaneta Semanišinová gave a talk on valued CSPs and their connection with resilience problems from database theory.
Applications
Two speakers gave talks on applications of CSPs to other areas in combinatorics and coding theory.
- Pravesh Kothari gave a talk on using a method based on k-XOR CSPs to resolve extremal combinatorial problems, including advances on the hypergraph Moore bound, lower bounds for locally decodable and correctable codes, and other applications.
- Xuandi Ren presented results on inapproximability for the problems of Nearest Code Word and Minimum Distance.
Creative Commons BY 4.0
Manuel Bodirsky, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný
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, and most recently topology) 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 20 years, research activity in this area has significantly intensified and hugely impressive progress was made.
The main topics addressed during the seminar will include complexity dichotomies for CSP and related problems, promise CSPs, approximability of CSPs, counting CSPs, and parameterized complexity of CSPs. The participants will also explore the interactions between these topics.
Manuel Bodirsky, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný
- Per Austrin (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Libor Barto (Charles University - Prague, CZ) [dblp]
- Arash Beikmohammadi (Simon Fraser University - Burnaby, CA)
- Amey Bhangale (University of California - Riverside, US) [dblp]
- Manuel Bodirsky (TU Dresden, DE) [dblp]
- Zarathustra Brady (Setauket, US) [dblp]
- Johanna Brunar (TU Wien, AT) [dblp]
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Silvia Butti (University of Oxford, GB) [dblp]
- Karthik C. S. (Rutgers University - New Brunswick, US) [dblp]
- Siu On Chan (Hong Kong, HK) [dblp]
- Victor Dalmau (UPF - Barcelona, ES) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Dmitry Feichtner-Kozlov (Universität Bremen, DE) [dblp]
- Florian Frick (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Venkatesan Guruswami (University of California - Berkeley, US) [dblp]
- Santiago Guzmán Pro (TU Dresden, DE)
- Maximilian Hadek (Charles University - Prague, CZ)
- Prahladh Harsha (TIFR - Mumbai, IN) [dblp]
- Johan Hastad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Peter Jonsson (Linköping University, SE) [dblp]
- Eun Jung Kim (KAIST - Daejeon, KR & CNRS - Paris, FR) [dblp]
- Pravesh K. Kothari (Princeton University, US) [dblp]
- Marcin Kozik (Jagiellonian University - Kraków, PL) [dblp]
- Andrei Krokhin (Durham University, GB) [dblp]
- Euiwoong Lee (University of Michigan - Ann Arbor, US) [dblp]
- Konstantin Makarychev (Northwestern University - Evanston, US) [dblp]
- Yury Makarychev (TTIC - Chicago, US) [dblp]
- Barnaby Martin (Durham University, GB) [dblp]
- Dániel Marx (CISPA - Saarbrücken, DE) [dblp]
- Antoine Mottet (TU Hamburg, DE) [dblp]
- Tomáš Nagy (Jagiellonian University - Kraków, PL) [dblp]
- Tamio-Vesa Nakajima (University of Oxford, GB)
- Jakub Opršal (University of Birmingham, GB) [dblp]
- George Osipov (Linköping University, SE) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michael Pinsker (TU Wien, AT) [dblp]
- Aaron Potechin (University of Chicago, US) [dblp]
- Xuandi Ren (University of California - Berkeley, US) [dblp]
- Jakub Rydval (TU Wien, AT) [dblp]
- Žaneta Semanišinová (TU Dresden, DE) [dblp]
- Santhoshini Velusamy (TTIC - Chicago, US)
- Uli Wagner (IST Austria - Klosterneuburg, AT) [dblp]
- Magnus Wahlström (Royal Holloway, University of London, GB) [dblp]
- Michal Wrona (Jagiellonian University - Kraków, PL) [dblp]
- Dmitriy Zhuk (Charles University - Prague, CZ) [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 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)
Classification
- Computational Complexity
- Data Structures and Algorithms
Keywords
- constraint satisfaction problem
- computational complexity
- hardness of approximation
- semidefinite programming
- parameterized complexity
