Parameterized Complexity of Constraint Satisfaction Problems

In a Valued Constraint Satisfaction Problem (VCSP), we are given a collection of constraints on a set of variables, with costs for breaking each constraint, and the goal is to assign values to the variables while minimizing the total cost.

A host of important optimization problems from many application areas such as artificial intelligence, bioinformatics, and operations research can be modeled as VCSPs. The VCSP is NP-hard, so we do not expect to solve it efficiently in full generality.

Thus, we focus on the natural regime where the cost is low compared to the number of constraints and study the complexity of solving VCSP parameterized by minimum solution cost. Current knowledge is fragmented and the lack of a unifying lens prohibits taking up greater challenges.

Our project aims to develop a general understanding of this problem using methods from algebra, graph theory, and optimization.

To increase short-term impact, we target problems that are highly relevant in application domains, such as graph homomorphisms, algebraic equations, and temporal reasoning formalisms in AI.A 3-year theoretical study will be carried out by the applicant while working as a postdoc with Stanislav Zivny at Oxford University and Magnus Wahlström at Royal Holloway University of London while cooperating with TCSLAB at LiU and the applicant´s network.

Four main directions will be pursued: finite- and infinite-domain VCSPs, approximation of VCSPs, and algebraic tools for parameterized complexity.