thesis
Complexity of constraint satisfaction
IST Austria Thesis
published
Michal
Rolinek
author 3CB3BC06-F248-11E8-B48F-1D18A9856A87
Vladimir
Kolmogorov
supervisor
VlKo
department
Discrete Optimization in Computer Vision: Theory and Practice
project
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).
https://research-explorer.app.ist.ac.at/download/992/4654/IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf
application/pdfno
https://research-explorer.app.ist.ac.at/download/992/6208/2017_Thesis_Rolinek_source.zip
application/zip
IST Austria2017
eng
10.15479/AT:ISTA:th_815
97
Rolinek, M. (2017). <i>Complexity of constraint satisfaction</i>. IST Austria. <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a>
M. Rolinek, <i>Complexity of constraint satisfaction</i>. IST Austria, 2017.
Rolinek, Michal. <i>Complexity of Constraint Satisfaction</i>. IST Austria, 2017. <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a>.
M. Rolinek, Complexity of Constraint Satisfaction, IST Austria, 2017.
Rolinek, Michal. <i>Complexity of Constraint Satisfaction</i>. IST Austria, 2017, doi:<a href="https://doi.org/10.15479/AT:ISTA:th_815">10.15479/AT:ISTA:th_815</a>.
Rolinek M. <i>Complexity of Constraint Satisfaction</i>. IST Austria; 2017. doi:<a href="https://doi.org/10.15479/AT:ISTA:th_815">10.15479/AT:ISTA:th_815</a>
Rolinek M. 2017. Complexity of constraint satisfaction, IST Austria, 97p.
9922018-12-11T11:49:35Z2020-01-16T12:38:34Z