NP-Completeness of Outcome Optimization for Partial CP-nets

Keith Purrington, Edmund H. Durfee

Partial CP-nets extend the standard CP-nets framework to allow users to express indifference about the values of some variables. Prior work has shown that linear-time forward sweep algorithms for outcome optimization in classic CP-nets can also be used with partial CP-nets when there is no evidence that fixes the values of one or more variables. In this paper we prove that, in the more general case where evidence is present, outcome optimization in partial CP-nets is, unfortunately, NP-complete. Fortunately, we are able to describe a polynomial-time backward sweep algorithm that finds optimal outcomes for a specialized class of partial CP-net structures (to be defined). Furthermore, by comparison to a GSAT-style random-walk algorithm and an exhaustive search, we empirically demonstrate that the backward sweep algorithm finds approximately optimal outcomes for general partial CP-nets and is faster by several orders of magnitude.

Subjects: 3.5 Qualitative Reasoning; 15.5 Decision Theory

Submitted: May 5, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.