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