# The Computational Complexity of Dominance and Consistency in CP-Nets

arXiv: https://arxiv.org/abs/1401.3453 · HTML: https://mlsanity.com/paper/1401.3453/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

## Built on by (most cited first, 5 of 5)

- [When Is It Acceptable to Break the Rules? Knowledge Representation of Moral Judgement Based on Empirical Data](https://mlsanity.com/paper/2201.07763/) (2022)
- [Even-if Explanations: Formal Foundations, Priorities and Complexity](https://mlsanity.com/paper/2401.10938/) (2024)
- [An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages](https://mlsanity.com/paper/2102.04107/) (2021)
- [Constrained Optimization with Qualitative Preferences](https://mlsanity.com/paper/2109.12179/) (2021)
- [Representing and Reasoning with Multi-Stakeholder Qualitative Preference Queries](https://mlsanity.com/paper/2307.16307/) (2023)

## Abstract (arXiv)

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined 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. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.