# Complexity of constraint satisfaction

Rolinek M. 2017. Complexity of constraint satisfaction. IST Austria.

IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf 786.14 KB

Thesis | Published | English
Supervisor
Department
Series Title
IST Austria Thesis
Abstract
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).
Publishing Year
Date Published
2017-05-01
Acknowledgement
FP7/2007-2013/ERC grant agreement no 616160
Page
97
IST-REx-ID

### Cite this

Rolinek M. Complexity of constraint satisfaction. 2017. doi:10.15479/AT:ISTA:th_815
Rolinek, M. (2017). Complexity of constraint satisfaction. IST Austria. https://doi.org/10.15479/AT:ISTA:th_815
Rolinek, Michal. “Complexity of Constraint Satisfaction.” IST Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.
M. Rolinek, “Complexity of constraint satisfaction,” IST Austria, 2017.
Rolinek M. 2017. Complexity of constraint satisfaction. IST Austria.
Rolinek, Michal. Complexity of Constraint Satisfaction. IST Austria, 2017, doi:10.15479/AT:ISTA:th_815.
All files available under the following license(s):
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
Open Access
2018-12-12
MD5 Checksum
81761fb939acb7585c36629f765b4373

Source File
File Name
Access Level
Closed Access