---
_id: '12563'
abstract:
- lang: eng
  text: 'he approximate graph coloring problem, whose complexity is unresolved in
    most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable,
    where c≥k. This problem naturally generalizes to promise graph homomorphism problems
    and further to promise constraint satisfaction problems. The complexity of these
    problems has recently been studied through an algebraic approach. In this paper,
    we introduce two new techniques to analyze the complexity of promise CSPs: one
    is based on topology and the other on adjunction. We apply these techniques, together
    with the previously introduced algebraic approach, to obtain new unconditional
    NP-hardness results for a significant class of approximate graph coloring and
    promise graph homomorphism problems.'
acknowledgement: "Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant
  EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
  No 101034413. Stanislav Živný was supported by a Royal Society University Research
  Fellowship. This project has received funding from the European Research Council
  (ERC) under the European Union’s Horizon 2020 research and innovation programme
  (grant agreement No 714532). The paper re\x1Eects only the authors’ views and not
  the views of the ERC or the European Commission. "
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Andrei
  full_name: Krokhin, Andrei
  last_name: Krokhin
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Marcin
  full_name: Wrochna, Marcin
  last_name: Wrochna
- first_name: Stanislav
  full_name: Živný, Stanislav
  last_name: Živný
citation:
  ama: Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise
    constraint satisfaction. <i>SIAM Journal on Computing</i>. 2023;52(1):38-79. doi:<a
    href="https://doi.org/10.1137/20m1378223">10.1137/20m1378223</a>
  apa: Krokhin, A., Opršal, J., Wrochna, M., &#38; Živný, S. (2023). Topology and
    adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>.
    Society for Industrial &#38; Applied Mathematics. <a href="https://doi.org/10.1137/20m1378223">https://doi.org/10.1137/20m1378223</a>
  chicago: Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology
    and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>.
    Society for Industrial &#38; Applied Mathematics, 2023. <a href="https://doi.org/10.1137/20m1378223">https://doi.org/10.1137/20m1378223</a>.
  ieee: A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction
    in promise constraint satisfaction,” <i>SIAM Journal on Computing</i>, vol. 52,
    no. 1. Society for Industrial &#38; Applied Mathematics, pp. 38–79, 2023.
  ista: Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in
    promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.
  mla: Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.”
    <i>SIAM Journal on Computing</i>, vol. 52, no. 1, Society for Industrial &#38;
    Applied Mathematics, 2023, pp. 38–79, doi:<a href="https://doi.org/10.1137/20m1378223">10.1137/20m1378223</a>.
  short: A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52
    (2023) 38–79.
date_created: 2023-02-16T07:03:52Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-08-01T13:11:30Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/20m1378223
ec_funded: 1
external_id:
  arxiv:
  - '2003.11351'
  isi:
  - '000955000000001'
intvolume: '        52'
isi: 1
issue: '1'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2003.11351
month: '01'
oa: 1
oa_version: Preprint
page: 38-79
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topology and adjunction in promise constraint satisfaction
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 52
year: '2023'
...
---
_id: '11991'
abstract:
- lang: eng
  text: The study of the complexity of the constraint satisfaction problem (CSP),
    centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in
    the last two decades. After a long concerted effort and many partial results,
    the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and
    Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP,
    has started to gain prominence. In this survey, we explain the importance of promise
    CSP and highlight many new very interesting features that the study of promise
    CSP has brought to light. The complexity classification quest for the promise
    CSP is wide open, and we argue that, despite the promise CSP being more general,
    this quest is rather more accessible to a wide range of researchers than the dichotomy-led
    study of the CSP has been.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Andrei
  full_name: Krokhin, Andrei
  last_name: Krokhin
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
citation:
  ama: Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem.
    <i>ACM SIGLOG News</i>. 2022;9(3):30-59. doi:<a href="https://doi.org/10.1145/3559736.3559740">10.1145/3559736.3559740</a>
  apa: Krokhin, A., &#38; Opršal, J. (2022). An invitation to the promise constraint
    satisfaction problem. <i>ACM SIGLOG News</i>. Association for Computing Machinery.
    <a href="https://doi.org/10.1145/3559736.3559740">https://doi.org/10.1145/3559736.3559740</a>
  chicago: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
    Satisfaction Problem.” <i>ACM SIGLOG News</i>. Association for Computing Machinery,
    2022. <a href="https://doi.org/10.1145/3559736.3559740">https://doi.org/10.1145/3559736.3559740</a>.
  ieee: A. Krokhin and J. Opršal, “An invitation to the promise constraint satisfaction
    problem,” <i>ACM SIGLOG News</i>, vol. 9, no. 3. Association for Computing Machinery,
    pp. 30–59, 2022.
  ista: Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction
    problem. ACM SIGLOG News. 9(3), 30–59.
  mla: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
    Satisfaction Problem.” <i>ACM SIGLOG News</i>, vol. 9, no. 3, Association for
    Computing Machinery, 2022, pp. 30–59, doi:<a href="https://doi.org/10.1145/3559736.3559740">10.1145/3559736.3559740</a>.
  short: A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.
date_created: 2022-08-27T11:23:37Z
date_published: 2022-07-01T00:00:00Z
date_updated: 2022-09-05T08:19:38Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3559736.3559740
external_id:
  arxiv:
  - '2208.13538'
intvolume: '         9'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/2208.13538
month: '07'
oa: 1
oa_version: Preprint
page: 30-59
publication: ACM SIGLOG News
publication_identifier:
  issn:
  - 2372-3491
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: An invitation to the promise constraint satisfaction problem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2022'
...