---
title: "The computational complexity of dominance and consistency in CP-nets"
authors:
  - "Judy Goldsmith"
  - "Jérôme Lang"
  - "Miroslaw Truszczynski"
  - "Nic Wilson"
doi: ""
url: "https://ijcai.org/proceedings/2005/70"
pdf: "https://ijcai.org/proceedings/2005/0070.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "144-148"
track: ""
keywords:
---

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

Judy Goldsmith, Jérôme Lang, Miroslaw Truszczynski, Nic Wilson

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 144-148.

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