NP-Completeness of Outcome Optimization for Partial CP-Nets

Abstract

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 CPnets 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 CPnet 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.