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 suggested that linear-time "forward-sweep" algorithms for outcome optimization in classic CP-nets can also be used with partial CP-nets. However, in this paper we prove that, in the general case where evidence is present, outcome optimization in partial CP-nets is, unfortunately, NP-complete. Fortunately, we are able to describe a linear-time "backward-sweep" algorithm that finds optimal outcomes for a restricted class of polytree- like partial CP-net structures. Furthermore, by comparison to a GSAT-style random-walk algorithm, we empirically demonstrate that the backward-sweep algorithm finds approximately optimal outcomes for general partial CP-nets.

Subjects: 3.5 Qualitative Reasoning; 15.5 Decision Theory

Submitted: Apr 8, 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.