{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:04:08Z","timestamp":1772237048807,"version":"3.50.1"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,12,29]],"date-time":"2015-12-29T00:00:00Z","timestamp":1451347200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Austrian Science Fund","award":["P 24285"],"award-info":[{"award-number":["P 24285"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>It is well known that the constraint satisfaction problem over a general\nrelational structure A is polynomial time equivalent to the constraint problem\nover some associated digraph. We present a variant of this construction and\nshow that the corresponding constraint satisfaction problem is logspace\nequivalent to that over A. Moreover, we show that almost all of the commonly\nencountered polymorphism properties are held equivalently on the A and the\nconstructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture\nas well as the conjectures characterizing CSPs solvable in logspace and in\nnondeterministic logspace are equivalent to their restriction to digraphs.<\/jats:p>","DOI":"10.2168\/lmcs-11(4:18)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T08:46:40Z","timestamp":1479718000000},"source":"Crossref","is-referenced-by-count":8,"title":["A finer reduction of constraint problems to digraphs"],"prefix":"10.46298","volume":"Volume 11, Issue 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5235-8715","authenticated-orcid":false,"given":"Jakub","family":"Bul\u00edn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dejan","family":"Delic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8149-1141","authenticated-orcid":false,"given":"Marcel","family":"Jackson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd","family":"Niven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2015,12,29]]},"reference":[{"key":"1038:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1619\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1619\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T16:08:03Z","timestamp":1681229283000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1619"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,29]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(4:18)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1406.6413","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1406.6413","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1811.11737","asserted-by":"subject"},{"id-type":"doi","id":"10.1007\/s00224-018-9905-y","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1811.11737","asserted-by":"subject"}],"has-preprint":[{"id-type":"doi","id":"10.32920\/21482265","asserted-by":"object"},{"id-type":"doi","id":"10.32920\/21482265.v1","asserted-by":"object"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,29]]},"article-number":"1619"}}