---
res:
bibo_abstract:
- "An instance of the Constraint Satisfaction Problem (CSP) is given by a finite
set of\r\nvariables, a finite domain of labels, and a set of constraints, each
constraint acting on\r\na subset of the variables. The goal is to find an assignment
of labels to its variables\r\nthat satisfies all constraints (or decide whether
one exists). If we allow more general\r\n“soft” constraints, which come with (possibly
infinite) costs of particular assignments,\r\nwe obtain instances from a richer
class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal
is to find an assignment with minimum total cost.\r\nIn this thesis, we focus
(assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity
of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent
of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage,
that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe
complexity classification modulo (missing pieces of) complexity classification
for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’
perfect\r\nmatching algorithm. This generalization contributes to complexity classfications
in two\r\nways. First, it gives a new (largest known) polynomial-time solvable
class of Boolean\r\nCSPs in which every variable may appear in at most two constraints
and second, it\r\nsettles full classification of Boolean CSPs with planar drawing
(again parametrized by a\r\nconstraint language).@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Michal
foaf_name: Rolinek, Michal
foaf_surname: Rolinek
foaf_workInfoHomepage: http://www.librecat.org/personId=3CB3BC06-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.15479/AT:ISTA:th_815
dct_date: 2017^xs_gYear
dct_language: eng
dct_publisher: IST Austria@
dct_title: Complexity of constraint satisfaction@
...