QCSP on reflexive tournaments

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

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