On the complexity of the CSP.

Abstract: 

The Constraint Satisfaction Problem (CSP) is defined as follows: we are given a set of variables, a set of values, and a set of constraints, where each constraint restricts the combination of values that certain tuple of variables can take. The question is whether there exists an assignment of values to the variables that satisfies all the constraints. The CSP is a well-known NP-complete problem, and hence much research has been done to identify restrictions of this problem that can be solved in polynomial time.

In this talk, we focus on the so-called structural restrictions, that limit the way the variables interact with each other through the constrains. We start by briefly surveying some landmark results characterizing polynomial-time solvable structural restrictions of the CSP. Then we consider the optimization version of the CSP, where the goal is to maximize the number of satisfied constraints (or the sum of the weights of the satisfied constraints in the weighted version). We present some results characterizing the structural restrictions that can be optimized in polynomial-time, which extend previous known results for the (decision version) CSP. We conclude discussing some results regarding approximability and some open problems. This talk is based on joint work with Standa Zivny, Clement Carbonnel and Marcin Wrochna.

Posted on Jun 10, 2025 in ACGO, Seminars