Back to Search Start Over

QCSP on Reflexive Tournaments

Authors :
Larose, Benoit
Markovic, Petar
Martin, Barnaby
Paulusma, Daniel
Smith, Siani
Zivny, Stanislav
Source :
ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022)
Publication Year :
2021

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 H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j 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.<br />Comment: arXiv admin note: text overlap with arXiv:1709.09486

Details

Database :
arXiv
Journal :
ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022)
Publication Type :
Report
Accession number :
edsarx.2104.10570
Document Type :
Working Paper
Full Text :
https://doi.org/10.1145/3508069