QCSP on reflexive tournaments

Larose, B.; Markovic, P.; Martin, B.; Paulusma, D.; Smith, S.; Zivny, S.

doi:10.4230/lipics.esa.2021.58

QCSP on reflexive tournaments

Larose, B.; Markovic, P.; Martin, B.; Paulusma, D.; Smith, S.; Zivny, S.

Authors

B. Larose

P. Markovic

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy

S. Zivny

Contributors

Petra Mutzel
Editor

Rasmus Pagh
Editor

Grzegorz Herman
Editor

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.

Citation

Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), . https://doi.org/10.4230/lipics.esa.2021.58

Conference Name	The 29th Annual European Symposium on Algorithms (ESA 2021)
Conference Location	Lisbon / Online
Start Date	Sep 6, 2021
End Date	Sep 8, 2021
Acceptance Date	Jun 23, 2021
Online Publication Date	Aug 31, 2021
Publication Date	2021
Deposit Date	Aug 23, 2021
Publicly Available Date	Sep 9, 2021
Pages	58:1-58:15
Series Title	Leibniz International Proceedings in Informatics
Series ISSN	1868-8969
DOI	https://doi.org/10.4230/lipics.esa.2021.58
Public URL	https://durham-repository.worktribe.com/output/1138544

Files

Accepted Conference Proceeding (759 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright 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. 58; pp. 58:1–58:15
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany