Complexity of constraint satisfaction problems - IST Austria 2017

Thesis

Acknowledgments Abstract 1 Introduction 2 Complexity of valued CSP 3 Generalizing Edmonds' algorithm A Appendices

An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of

variables, a finite domain of labels, and a set of constraints, each constraint acting on

a subset of the variables. The goal is to find an assignment of labels to its variables

that satisfies all constraints (or decide whether one exists). If we allow more general

“soft” constraints, which come with (possibly infinite) costs of particular assignments,

we obtain instances from a richer class called Valued Constraint Satisfaction Problem

(VCSP). There the goal is to find an assignment with minimum total cost.

In this thesis, we focus (assuming that P

6

=

NP) on classifying computational com-

plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core

content of the work. In one of them, we consider VCSPs parametrized by a constraint

language, that is the set of “soft” constraints allowed to form the instances, and finish

the complexity classification modulo (missing pieces of) complexity classification for

analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect

matching algorithm. This generalization contributes to complexity classfications in two

ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean

CSPs in which every variable may appear in at most two constraints and second, it

settles full classification of Boolean CSPs with planar drawing (again parametrized by a

constraint language).