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: | |
| Look up in GoogleScholar |
