---
_id: '992'
abstract:
- lang: eng
  text: "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)."
acknowledgement: FP7/2007-2013/ERC grant agreement no 616160
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Michal
  full_name: Rolinek, Michal
  id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
  last_name: Rolinek
citation:
  ama: Rolinek M. Complexity of constraint satisfaction. 2017. doi:<a href="https://doi.org/10.15479/AT:ISTA:th_815">10.15479/AT:ISTA:th_815</a>
  apa: Rolinek, M. (2017). <i>Complexity of constraint satisfaction</i>. Institute
    of Science and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a>
  chicago: Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of
    Science and Technology Austria, 2017. <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a>.
  ieee: M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science
    and Technology Austria, 2017.
  ista: Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science
    and Technology Austria.
  mla: Rolinek, Michal. <i>Complexity of Constraint Satisfaction</i>. Institute of
    Science and Technology Austria, 2017, doi:<a href="https://doi.org/10.15479/AT:ISTA:th_815">10.15479/AT:ISTA:th_815</a>.
  short: M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and
    Technology Austria, 2017.
date_created: 2018-12-11T11:49:35Z
date_published: 2017-05-01T00:00:00Z
date_updated: 2023-09-07T12:05:41Z
day: '01'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:th_815
ec_funded: 1
file:
- access_level: open_access
  checksum: 81761fb939acb7585c36629f765b4373
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:07:55Z
  date_updated: 2020-07-14T12:48:18Z
  file_id: '4654'
  file_name: IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf
  file_size: 786145
  relation: main_file
- access_level: closed
  checksum: 2b2d7e1d6c1c79a9795a7aa0f860baf3
  content_type: application/zip
  creator: dernst
  date_created: 2019-04-05T08:43:24Z
  date_updated: 2020-07-14T12:48:18Z
  file_id: '6208'
  file_name: 2017_Thesis_Rolinek_source.zip
  file_size: 5936337
  relation: source_file
file_date_updated: 2020-07-14T12:48:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '97'
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6407'
pubrep_id: '815'
status: public
supervisor:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
title: Complexity of constraint satisfaction
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...