NP-Completeness of Outcome Optimization for Partial CP-Nets

Keith Purrington, Edmund H. DurfeeAAAI 2008

Abstract

Conditional Preference networks (CP-nets) are a widely used framework for representing and reasoning with qualitative preferences. While finding optimal outcomes in standard, fully-specified CP-nets is computationally efficient, real-world applications often involve indifference and external constraints. This paper, originally presented at AAAI 2008, investigates the computational boundaries of Partial CP-nets. We prove that the problem of finding an optimal outcome becomes NP-complete once external evidence is introduced. Furthermore, we propose a three-step "sweep" algorithm that provides efficient, high-quality approximations for general cases and optimal solutions for specific structural classes.

Introduction

Modeling human preferences often requires capturing conditional dependencies, such as "I prefer red wine if I'm eating meat, but white wine if I'm eating fish." CP-nets provide an intuitive graphical representation for these dependencies. In a standard CP-net, identifying the most preferred outcome is a linear task achievable via a simple forward sweep: one simply selects the most preferred value for each variable in the order of their dependencies.

However, users are frequently indifferent about certain choices—for example, not caring whether a meeting is held in the morning or afternoon. Partial CP-nets were developed to accommodate this "unranked" indifference. While previous research suggested that optimization in Partial CP-nets remained easy if the agent controlled all variables, this paper addresses the "gap" created by external evidence.

A Partial CP-net where indifference at a higher-level variable (D) affects the optimal choice for a dependent variable (W).

External evidence represents constraints beyond the agent's control, such as a restaurant being out of a specific wine. When some variables are fixed by external factors, an indifferent choice made early in the decision process might "trap" the agent into a sub-optimal outcome later.

Complexity Analysis

The core contribution of this paper is the formal proof that outcome optimization for Partial CP-nets with evidence is NP-complete.

Hardness Proof via 3SAT Reduction

The authors establish NP-completeness by reducing the 3-Satisfiability (3SAT) problem to the problem of finding an optimal outcome in a restricted class of Partial CP-nets. They demonstrate that even in a simplified bipartite graph structure—where a set of unranked nodes (representing indifferent choices) points to a set of evidence nodes—the problem remains computationally hard.

The bipartite graph structure used to reduce 3SAT to the Partial CP-net optimization problem, featuring unranked nodes (I) and evidence nodes (E).

This reduction shows that indifference is deceptive; while it might seem to simplify the problem by reducing the number of strict preferences, it actually creates "branches" in the decision tree. Navigating these branches correctly under external constraints requires either backtracking or global "omniscience," leading to the observed complexity.

The "Single Path" Structural Exception

The authors identify a specific structural "sweet spot" where the problem remains tractable. If every unranked node in the network has at most one path to an evidence node, the problem can be solved optimally in polynomial time. This finding suggests that the complexity is driven by the interconnectedness of indifferent choices and their downstream constraints.

The Three-Step Sweep Algorithm

To address the NP-completeness of the general case, the authors propose a heuristic three-step algorithm designed to balance efficiency and solution quality:

  1. Initial Forward Sweep: The algorithm first assigns values to variables that are independent of the unranked (indifferent) nodes.
  2. Backward Sweep: Working backward from the fixed evidence nodes, the algorithm determines the best settings for the unranked nodes. This step effectively "looks ahead" to see how indifferent choices will impact the satisfaction of downstream preferences given the known constraints.
  3. Final Forward Sweep: The algorithm completes the assignment for the remaining dependent variables based on the choices made in the previous steps.

This algorithm is provably optimal for the "single path" cases and serves as a powerful heuristic for more complex, highly interconnected networks.

Empirical Evaluation

The paper evaluates the proposed algorithm using both synthetic bipartite networks (designed to mirror the 3SAT reduction) and more general Partial CP-nets. The three-step sweep was compared against baseline search methods, including GSAT-style random-walk algorithms.

The results indicate that the proposed algorithm significantly outperforms stochastic search. It was found to be "many times faster" while consistently identifying outcomes that were more preferred (or at least as preferred) as those found by the baselines. This suggests that the structured "look-ahead" provided by the backward sweep is far more effective than random exploration in these constrained preference spaces.

Conclusion

This research highlights a critical transition in the complexity of preference reasoning. While qualitative modeling via CP-nets is often efficient, the combination of indifference and external constraints necessitates more sophisticated algorithmic approaches. The three-step sweep algorithm provides a practical path forward for building responsive preference-based systems in domains like automated scheduling and product configuration. Future work remains to explore these dynamics in high-cardinality domains where variables can take on many possible values.

Summary updated

BibTeX
@inproceedings{purrington2008np,
  author = {Keith Purrington and Edmund H. Durfee},
  title = {{NP-Completeness of Outcome Optimization for Partial CP-Nets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure