Description
A myriad of computational problems, ranging from Boolean satisfiability and systems of equations to graph coloring and homomorphism, can be formulated as satisfying a collection of constraints on a shared set of variables, and thus can be modeled as constraint satisfaction problems (CSPs). The CSP and its variants are commonly studied under two different perspectives, namely structural and semantic restrictions. In the first case, one restricts interactions between the variables and the constraints (e.g., by bounding the treewidth of the associated primal graph) and is usually interested in the parameterized complexity of the problem. Combinatorial arguments and structural graph theory are prevalent in this direction. In the second case, one restricts the constraint types, or more precisely, the set of relations that can be imposed by the constraints. This line of research has mostly been concerned with the polynomial-time complexity of the CSP and relies on tools from universal algebra, model theory, and logic. The goal of the workshop is to bring together these two research communities to facilitate an exchange of ideas and tools.
The workshop is motivated by a series of exciting recent developments in the intersection of parameterized complexity and constraint satisfaction. New connections between graph width parameters and the CSP have been discovered in light of recent progress in parameterized complexity theory. Algorithmic breakthroughs in graph separation and transversal problems have reinvigorated the study of MinCSP parameterized by the solution cost. In a related development, reductions into CSP with few variables have been successfully applied in resolving open problems, and a new width parameter for graphs and matrices called twinwidth was employed in dealing with the resulting CSPs.
The workshop includes two tutorials: one on the algebraic approach to the CSP and another on the parameterized complexity toolbox for CSPs. It also hosts several survey talks on the topics including
- MinCSP parameterized by the solution cost,
- graph homomorphisms,
- kernelization & sparsification,
- structural restrictions,
as well as an open problem session. The workshop is co-located with LiCS/ICALP/FSCD 2024.
Confirmed Invited Speakers
- Andrei Krokhin, Durham University, UK
- Dániel Marx, CISPA Helmholz Center for Information Security, Saarbrücken, Germany
- Marcin Pilipczuk, University of Warsaw, Poland
- Paweł Rzążewski, Warsaw University of Technology, Poland
- Magnus Wahlström, Royal Holloway University of London, UK
- Standa Živný, Oxford University, UK
Schedule
| Time | Speaker | Title |
|---|---|---|
| 09:00 - 10:00 | Dániel Marx | Constraint Satisfaction and Fixed-Parameter Tractability |
| 10:00 - 10:30 | First coffee break ☕ | |
| 10:30 - 11:30 | Andrei Krokhin | A Theory of Gadget Reductions for CSPs |
| 11:30 - 11:45 | Short break | |
| 11:45 - 12:30 | Magnus Wahlström | Sparsification and Running Time Aspects of CSPs |
| 12:30 - 14:00 | Lunch 🥪 | |
| 14:00 - 14:45 | Marcin Pilipczuk | Parametrized Complexity of CSPs Parameterized by the Number of Unsatisfied Constraints |
| 14:45 - 15:30 | Standa Živný | PTAS for CSPs from the Other Side |
| 15:30 - 16:00 | Second coffee break ☕ | |
| 16:00 - 16:45 | Paweł Rzążewski | CSPs for Children: Fine-Grained Complexity of the Graph Homomorphism Problem |
| 16:45 - 18:00 | Open problems |
Open Problems
Organizers
- Dániel Marx, CISPA Helmholz Center for Information Security, Saarbrücken, Germany
- George Osipov, Linköping University, Sweden
- Roohani Sharma, University of Bergen, Norway
- Magnus Wahlström, Royal Holloway University of London, UK