Algorithmic techniques for constraint satisfaction problems over finitely bounded homogeneous structures

Abstract

A Constraint Satisfaction Problem (CSP) over a relational structure A is the problem where one is given an instance – i.e., a finite set of variables and constraints, and one has to decide whether there exists an assignment of the values from the domain of A to the variables such that all constraints are satisfied. In this thesis, we deal with CSPs over structures which are first-order definable in finitely bounded homogeneous structures (so-called first-order reducts of these structures). While homogeneity assures us that every solution of a CSP instance is up to automorphisms given by the relations holding on its image, finite boundedness implies that every solution must only be verified locally on subsets of a fixed size.In Chapter 1, we give an introduction to the theory of CSPs and we discuss related concepts from model theory and universal algebra that are be needed in the rest of the thesis. Local consistency checking is one of the most important algorithmic techniques in the area of constraint satisfaction. In Chapter 2, we prove an upper bound on the amount of local consistency needed to solve CSPs over first-order reducts of finitely bounded homogeneous structures which satisfy certain algebraic conditions. As a corollary, we obtain a bound on the amount of local consistency needed to solve CSPs over first-order reducts of many well-known relational structures which are solvable by local consistency checking. We also obtain a characterization of bounded width for first-order reducts of unary structures andfor certain structures related to the logic MMSNP. In Chapter 3, we consider CSPs over first-order reducts of certain uniform hypergraphs. It was observed in [73] that these CSPs cannot be solved by standard methods used in most known classifications of CSPs of first-order reducts of finitely bounded homogeneous structures. Therefore, we introduce a new algorithm for solving the CSPs under consideration. This algorithm uses reformulations of several notions used in the algorithm for solving all tractable CSPs over finite domains from [83, 84]. In Chapter 4, we consider a class of first-order reducts of finitely bounded homogeneous structures that are solvable by a stronger form of local consistency. We prove that these structures have limited expressibility in the form of implicational simplicity. This will imply that only a restricted amount of local consistency checking is needed in order to solve their CSPs. Chapter 2 corresponds to the publication [72] (with Antoine Mottet, Michael Pinsker andMicha l Wrona) which is a journal version of [71]; Chapter 3 corresponds to the publication [70] (with Antoine Mottet and Michael Pinsker); Chapter 4 is based on results that have not been published yet and that were obtained in collaboration with Michael Pinsker.