QCSP on reflexive tournaments

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

doi:10.1145/3508069

QCSP on reflexive tournaments

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

Authors

B. Larose

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

P. Markovic

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

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

S. Zivny

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

Citation

Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069

Journal Article Type	Article
Acceptance Date	Dec 1, 2021
Online Publication Date	Apr 6, 2022
Publication Date	2022-07
Deposit Date	Dec 31, 2021
Publicly Available Date	Jan 4, 2022
Journal	ACM Transactions on Computational Logic
Print ISSN	1529-3785
Electronic ISSN	1557-945X
Publisher	Association for Computing Machinery (ACM)
Peer Reviewed	Peer Reviewed
Volume	23
Issue	3
Article Number	14
Pages	1-22
DOI	https://doi.org/10.1145/3508069
Public URL	https://durham-repository.worktribe.com/output/1218904

Files

Accepted Journal Article (725 Kb)
PDF

Copyright 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