Constraint satisfaction problems (CSPs) are a class of decision problems that appear in many areas of computer science. A CSP is parameterized by a relational structure B over a finite signature called the template. The input of the CSP of B is a set of constraints over variables, and the output is whether values from the domain of B can be assigned to the variables in a way that simultaneously satisfies all constraints. The framework can be generalized to simulate optimization problems. In this case, the relations of B are replaced by cost functions, the input contains additionally a threshold and instead of deciding satisfiability, we decide whether there is an assignment whose cost is bounded by the threshold; such problems are called valued CSPs (VCSPs). VCSPs on finite domains are known to exhibit a complexity dichotomy: they are in P or NP- complete. However, many natural optimization problems, such as the minimum feedback arc set problem or the min-correlation-clustering problem cannot be modeled over a finite domain.
Motivated by the progress in the area of infinite-domain CSPs, we study VCSPs on infinite domains. We take inspiration from the model-theoretic restrictions important in CSPs and focus on templates that have an oligomorphic automorphism group. The project aims to classify the complexity for relevant subclasses of VCSPs of such templates, explore the algebraic theory of VCSPs and apply this knowledge to problems that can be modeled as VCSPs such as resilience problems from database theory. We combine methods from finite-domain VCSPs with the model-theoretic approach to infinite-domain CSPs and adapt them to the unique setting we study. We exploit the connection between gadget reductions for VCSPs based on the concepts of expressibility and pp-constructability and the symmetries of the templates, so-called fractional polymorphisms.
VCSPs on infinite domains have been studied only scarcely and therefore this project opens new horizons in the area of constraint satisfaction problems and computational complexity of optimization problems. We expect to further develop the algebraic framework for infinite-domain VCSPs and significantly improve the understanding of the connection of the algebraic properties to their complexity. This may lead to a systematic approach to classifying complexity in classes of optimization problems that were difficult to study before.
