Skip to main content

Research Repository

Advanced Search

Quantified Constraint Satisfaction Problem on semicomplete digraphs

Đapić, Petar; Marković, Petar; Martin, Barnaby

Quantified Constraint Satisfaction Problem on semicomplete digraphs Thumbnail


Authors

Petar Đapić

Petar Marković



Abstract

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.

Citation

Đapić, P., Marković, P., & Martin, B. (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic, 18(1), Article 2. https://doi.org/10.1145/3007899

Journal Article Type Article
Acceptance Date Oct 12, 2016
Online Publication Date Apr 13, 2017
Publication Date Apr 13, 2017
Deposit Date Oct 14, 2016
Publicly Available Date Oct 17, 2016
Journal ACM Transactions on Computational Logic
Print ISSN 1529-3785
Electronic ISSN 1557-945X
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 18
Issue 1
Article Number 2
DOI https://doi.org/10.1145/3007899
Public URL https://durham-repository.worktribe.com/output/1402851

Files

Accepted Journal Article (547 Kb)
PDF

Copyright 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), https://doi.org/10.1145/3007899.






You might also like



Downloadable Citations