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:

QCSP on reflexive tournaments

Larose, B. and Martin, B. and Markovic, P. and Paulusma, D. and Smith, S. and Živný, S. (2022) 'QCSP on reflexive tournaments.', ACM Transactions on Computational Logic, 23 (3). pp. 1-22.


We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components H1,…,Hn so that there exists an edge from every vertex of Hi to every vertex of Hj if and only if i<j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:© 2022 Association for Computing Machinery | ACM 2022. 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,
Date accepted:01 December 2021
Date deposited:04 January 2022
Date of first online publication:06 April 2022
Date first made open access:04 January 2022

Save or Share this output

Look up in GoogleScholar