2026-08-09T06:30:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25276 2026-02-09T12:33:43Z ddc:004 open_access

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 25211) Bodirsky, Manuel Guruswami, Venkatesan Marx, Dániel Živný, Stanislav Semanišinová, Žaneta computational complexity constraint satisfaction problem hardness of approximation parameterized complexity semidefinite programming 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, etc.). 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 Dagstuhl Seminar 25211 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP so that they can share their insights obtained during the past four years. This report documents the material presented during the course of the seminar. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Venkatesan Guruswami and Dániel Marx and Stanislav Živný and Žaneta Semanišinová 2025 Is Part Of Dagstuhl Reports, Volume 15, Issue 5 (2025) Article Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagRep.15.5.114 urn:nbn:de:0030-drops-252762 https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.5.114 eng https://creativecommons.org/licenses/by/4.0/legalcode