QCSP on partially reflexive forests

Conference paper

Martin, B. 2011. QCSP on partially reflexive forests. The 17th International Conference on Principles and Practice of Constraint Programming (CP 2011). Perugia, Italy 12 - 16 Sep 2011 Springer. pp. 546-560 https://doi.org/10.1007/978-3-642-23786-7_42
TypeConference paper
TitleQCSP on partially reflexive forests
AuthorsMartin, B.
Abstract

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive forests. We obtain a complexity-theoretic dichotomy: QCSP(H) is either in NL or is NP-hard. The separating condition is related firstly to connectivity, and thereafter to accessibility from all vertices of H to connected reflexive subgraphs. In the case of partially reflexive paths, we give a refinement of our dichotomy: QCSP(H) is either in NL or is Pspace-complete.

Research GroupFoundations of Computing group
ConferenceThe 17th International Conference on Principles and Practice of Constraint Programming (CP 2011)
Page range546-560
ISSN0302-9743
ISBN
Hardcover9783642237850
PublisherSpringer
Publication dates
Print2011
Publication process dates
Deposited16 Jan 2013
Output statusPublished
Additional information

Martin B. (2011) QCSP on Partially Reflexive Forests. In: Lee J. (eds) Principles and Practice of Constraint Programming – CP 2011. CP 2011. Lecture Notes in Computer Science, vol 6876. Springer, Berlin, Heidelberg

Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-642-23786-7_42
LanguageEnglish
Book titlePrinciples and Practice of Constraint Programming – CP 2011
Permalink -

https://repository.mdx.ac.uk/item/83x18

Log in to edit
  • 24
    total views
  • 0
    total downloads
  • 3
    views this month
  • 0
    downloads this month

Export as