ECAI 2004 Conference Paper

Quantified Constraint Satisfaction and Bounded Treewidth

Hubie Chen

In previous work, it has been shown that instances of the constraint satisfaction problem with bounded treewidth are tractable. We investigate, for the first time, the restriction of bounded treewidth in the setting of the quantified constraint satisfaction problem (QCSP). We demonstrate a tractability result, namely, that instances of the QCSP with bounded treewidth, bounded quantifier alternations, and bounded domain size are tractable.

Keywords: quantified constraint satisfaction, tractability, bounded treewidth

Citation: Hubie Chen: Quantified Constraint Satisfaction and Bounded Treewidth. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.161-165.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).