[{"abstract":[{"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.","lang":"eng"}],"date_updated":"2023-08-01T13:11:30Z","oa_version":"Preprint","month":"01","type":"journal_article","page":"38-79","date_created":"2023-02-16T07:03:52Z","volume":52,"year":"2023","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\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","_id":"12563","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"date_published":"2023-01-01T00:00:00Z","external_id":{"isi":["000955000000001"],"arxiv":["2003.11351"]},"status":"public","citation":{"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.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","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>","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>."},"intvolume":"        52","day":"01","author":[{"full_name":"Krokhin, Andrei","last_name":"Krokhin","first_name":"Andrei"},{"orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","last_name":"Opršal","first_name":"Jakub"},{"last_name":"Wrochna","first_name":"Marcin","full_name":"Wrochna, Marcin"},{"first_name":"Stanislav","last_name":"Živný","full_name":"Živný, Stanislav"}],"title":"Topology and adjunction in promise constraint satisfaction","arxiv":1,"department":[{"_id":"UlWa"}],"publisher":"Society for Industrial & Applied Mathematics","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","ec_funded":1,"article_processing_charge":"No","article_type":"original","publication":"SIAM Journal on Computing","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"quality_controlled":"1","doi":"10.1137/20m1378223","project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413"}],"language":[{"iso":"eng"}],"issue":"1","isi":1,"keyword":["General Mathematics","General Computer Science"]},{"date_published":"2022-07-01T00:00:00Z","main_file_link":[{"url":"http://arxiv.org/abs/2208.13538","open_access":"1"}],"publication_status":"published","oa":1,"intvolume":"         9","citation":{"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>.","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>","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>","short":"A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.","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.","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>."},"status":"public","external_id":{"arxiv":["2208.13538"]},"volume":9,"date_created":"2022-08-27T11:23:37Z","page":"30-59","type":"journal_article","oa_version":"Preprint","month":"07","abstract":[{"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.","lang":"eng"}],"date_updated":"2022-09-05T08:19:38Z","_id":"11991","year":"2022","doi":"10.1145/3559736.3559740","quality_controlled":"1","publication_identifier":{"issn":["2372-3491"]},"issue":"3","language":[{"iso":"eng"}],"title":"An invitation to the promise constraint satisfaction problem","arxiv":1,"author":[{"full_name":"Krokhin, Andrei","first_name":"Andrei","last_name":"Krokhin"},{"first_name":"Jakub","last_name":"Opršal","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","orcid":"0000-0003-1245-3456"}],"day":"01","publication":"ACM SIGLOG News","article_type":"original","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Association for Computing Machinery","department":[{"_id":"UlWa"}]}]