On Sufficient Conditions for Consistency Checking in CP-theory Preferences

Checking consistency of qualitative preferences in CP-theory is PSPACE-complete in general. Building on Wilson’s seminal work on Complete Search (cs) tree based sufficient conditions for preferences, we characterize the necessary and sufficient conditions for the existence of a cs-tree, yielding the weakest sufficient condition for cs-tree–based consistency, and demonstrate that testing consistency under this condition is coNP-complete. Additionally, we present a polynomial-time computable upper approximation of the dominance relation for cs-tree–consistent CP-theory preferences, and prove that it subsumes all previously proposed approximations. Finally, we introduce set-labeled cs-trees, a generalization of cs-trees, which characterizes necessary and sufficient conditions for consistency checking in CP-theory preferences.