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.
Abstract

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
ISSN0302-9743
ISBN
Hardcover9783662439470
PublisherSpringer
Publication dates
Print2014
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
LanguageEnglish
Book titleAutomata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I
Permalink -

https://repository.mdx.ac.uk/item/858q0

Log in to edit

Download files

Accepted author manuscript
webICALP2014.pdf

  • 16
    total views
  • 7
    total downloads
  • 1
    views this month
  • 1
    downloads this month

Export as