Exploiting Structure in CSP-related Problems

Sammanfattning: In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. The constraints specify a set of variables and associated local conditions on the domain values allowed for each variable, and the objective of a CSP is to assign domain values to the variables, subject to these constraints.The first main part of the thesis is concerned with studying restrictions on the structure induced by the constraints on the variables for different computational problems related to the CSP. In particular, we examine how to exploit various graph, and hypergraph, acyclicity measures from the literature to find classes of relational structures for which our computational problems become efficiently solvable. Among the problems studied are, such where, in addition to the constraints of a CSP, lists of allowed domain values for each variable are specified (LHom). We also study variants of the CSP where the objective is changed to: counting the number of possible assignments of domain values to the variables given the constraints of a CSP (#CSP), minimising or maximising the cost of an assignment satisfying all constraints given various different ways of assigning costs to assignments (MinHom, Max Sol, and CSP), or maximising the number of satisfied constraints (Max CSP). In several cases, our investigations uncover the largest known (or possible) classes of relational structures for which our problems are efficiently solvable. Moreover, we take a different view on our optimisation problems MinHom and VCSP; instead of considering fixed arbitrary values for some (hyper)graph acyclicity measure associated with the underlying CSP, we consider the problems parameterised by such measures in combination with other basic parameters such as domain size and maximum arity of constraints. In this way, we identify numerous combinations of the considered parameters which make these optimisation problems admit fixed-parameter algorithms.In the second part of the thesis, we explore the approximability properties of the (weighted) Max CSP problem for graphs. This is a problem which is known to be approximable within some constant ratio, but not believed to be approximable within an arbitrarily small constant ratio. Thus it is of interest to determine the best ratio within which the problem can be approximated, or at least give some bound on this constant. We introduce a novel method for studying approximation ratios which, in the context of Max CSP for graphs, takes the form of a new binary parameter on the space of all graphs. This parameter may, informally, be thought of as a sort of distance between two graphs; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other.