QCSP on reflexive tournaments

Larose, B.; Markovic, P.; Martin, B.; 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 < 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, September). QCSP on reflexive tournaments. Presented at The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online

• Presentation Conference Type: Conference Paper (published)
• Conference Name: The 29th Annual European Symposium on Algorithms (ESA 2021)
• 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