QCSP on semicomplete digraphs

Conference paper

Dapić, P., Marković, P. and Martin, B. 2014. QCSP on semicomplete digraphs. 41st International Colloquium on Automata, Languages and Programming, ICALP 2014. Copenhagen, Denmark 08 - 11 Jul 2014 Springer. pp. 847-858
TypeConference paper
TitleQCSP on semicomplete digraphs
AuthorsDapić, P., Marković, P. and Martin, B.

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 semicompletes enjoy only essentially unary polymorphisms, which is combinatorially interesting in its own right.

Research GroupFoundations of Computing group
Conference41st International Colloquium on Automata, Languages and Programming, ICALP 2014
Page range847-858
Publication dates
Publication process dates
Deposited03 Jun 2015
Output statusPublished
Accepted author manuscript
Copyright Statement

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-43948-7_70

Additional information

Online ISBN: 9783662439487
Published paper appears in: Automata, Languages, and Programming, Volume 8572 of the series Lecture Notes in Computer Science pp 847-858, 2014

Web address (URL)http://dx.doi.org/10.1007/978-3-662-43948-7_70
Book titleAutomata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I
Permalink -


Download files

Accepted author manuscript
  • 15
    total views
  • 3
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as