The computational complexity of dominance and consistency in CP-nets

Judy Goldsmith, Jérôme Lang, Miroslaw Truszczyński, Nic Wilson

Research output: Contribution to journalConference articlepeer-review

32 Scopus citations

Abstract

We investigate the computational complexity of testing dominance and consistency in CP-nets. Up until now, the complexity of dominance has been determined only for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. We show here that both dominance and consistency testing for general CP-nets are PSPACE-complete. The reductions used in the proofs are from STRIPS planning, and thus establish strong connections between both areas.

Original languageEnglish
Pages (from-to)144-149
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2005
Event19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom
Duration: Jul 30 2005Aug 5 2005

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'The computational complexity of dominance and consistency in CP-nets'. Together they form a unique fingerprint.

Cite this