We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Quantified constraint satisfaction problem on semicomplete digraphs.

Đapić, Petar and Marković, Petar and Martin, Barnaby (2017) 'Quantified constraint satisfaction problem on semicomplete digraphs.', ACM transactions on computational logic., 18 (1). p. 2.


We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(H) is either in P, is NP-complete, or is Pspace-complete. The largest part of our work is the algebraic classification of precisely which semicomplete digraphs enjoy only essentially unary polymorphisms, which is combinatorially interesting in its own right.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:© 2017 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic, 18, 1, Article 2 (April 2017),
Date accepted:12 October 2016
Date deposited:17 October 2016
Date of first online publication:13 April 2017
Date first made open access:13 April 2017

Save or Share this output

Look up in GoogleScholar