The computational complexity of dominance and consistency in CP-nets

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

The computational complexity of dominance and consistency in CP-nets

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

University of Kentucky
Universit́e Paul Sabatier/CNRS

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	144-149
Number of pages	6
Journal	IJCAI International Joint Conference on Artificial Intelligence
Publication status	Published - 2005
Event	19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom Duration: 30 Jul 2005 → 5 Aug 2005

Cite this

@article{0c397ae71cc44163b35231bc66d51e59,

title = "The computational complexity of dominance and consistency in CP-nets",

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.",

author = "Judy Goldsmith and J{\'e}r{\^o}me Lang and Miroslaw Truszczy{\'n}ski and Nic Wilson",

year = "2005",

language = "English",

pages = "144--149",

journal = "IJCAI International Joint Conference on Artificial Intelligence",

issn = "1045-0823",

publisher = "International Joint Conferences on Artificial Intelligence",

note = "19th International Joint Conference on Artificial Intelligence, IJCAI 2005 ; Conference date: 30-07-2005 Through 05-08-2005",

}

TY - JOUR

T1 - The computational complexity of dominance and consistency in CP-nets

AU - Goldsmith, Judy

AU - Lang, Jérôme

AU - Truszczyński, Miroslaw

AU - Wilson, Nic

PY - 2005

Y1 - 2005

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

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

UR - https://www.scopus.com/pages/publications/84880740195

M3 - Article

AN - SCOPUS:84880740195

SN - 1045-0823

SP - 144

EP - 149

JO - IJCAI International Joint Conference on Artificial Intelligence

JF - IJCAI International Joint Conference on Artificial Intelligence

T2 - 19th International Joint Conference on Artificial Intelligence, IJCAI 2005

Y2 - 30 July 2005 through 5 August 2005

ER -

The computational complexity of dominance and consistency in CP-nets

Abstract

Other files and links

Fingerprint

Cite this