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 Markovic, P. and Martin, B. and Paulusma, D. and Smith, S. and Zivny, S. (2021) 'QCSP on reflexive tournaments.', The 29th Annual European Symposium on Algorithms (ESA 2021) Lisbon / Online, 6-8 Sept 2021.

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:Conference item (Paper)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution 4.0.
Download PDF
(742Kb)
Status:Peer-reviewed
Publisher Web site:https://drops.dagstuhl.de/opus/institut_lipics.php
Publisher statement:© Benoît Larose, Peter Marković, Barnaby Martin, Daniël Paulusma, Siani Smith and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0 29th Annual European Symposium on Algorithms (ESA 2021). Editors: Petra Mutzel, Rasmus Pagh, and Grzegorz Herman; Article No. 2; pp. 2:1–2:15 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Date accepted:23 June 2021
Date deposited:25 August 2021
Date of first online publication:2021
Date first made open access:09 September 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar