Quantified Constraint Satisfaction Problem on Semicomplete Digraphs
Petar Djapic, Petar Marković, Barnaby D. Martin · ACM Transactions on Computational Logic · 2017
We study the (non-uniform) quantified constraint satisfaction problem QCSP( H ) as H ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP( H ) is either in P, is NP-complete, or is Pspace-complete. The largest part of our work is the algebraic classification of precisely which semicomplete digraphs enjoy only essentially unary polymorphisms, which is combinatorially interesting in its own right.