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 will include two tutorials: one on the algebraic approach to the CSP and another on the parameterized complexity toolbox for CSPs. It will also host 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

Location and Schedule

Room TBD, Astra building on the campus of Tallinn University, Narva mnt 29, Tallinn, Estonia

Registration

For official registration, please go to LiCS/ICALP/FSCD. Please also fill in this registration-of-interest form for the organizers to estimate the number of participants.

Organizers

• Dániel Marx, CISPA Helmholz Center for Information Security, Saarbrücken, Germany
• George Osipov, unaffiliated, Georgia
• Roohani Sharma, University of Bergen, Norway
• Magnus Wahlström, Royal Holloway University of London, UK