Cookies

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.

Abstract

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
(708Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1145/3508069
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, https://doi.org/10.1145/3508069
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

Export:
Export
Look up in GoogleScholar