A Parameterized Complexity Analysis of Generalized CP-Nets

Martin Kronegger, Martin Lackner, Andreas Pfandler, Reinhard PichlerAAAI 2014 · DOI

Introduction

Representing preferences is a fundamental challenge in artificial intelligence. Generalized CP-nets (GCP-nets) offer a powerful and succinct formalism for modeling conditional preferences, such as "I prefer a red car over a blue one, if it is a sports car." However, this expressive power comes with significant computational costs. The Dominance problem—determining if one outcome is preferred over another—is PSPACE-complete, placing it in the same complexity class as the most difficult problems in classical planning.

To address this, we apply parameterized complexity analysis to identify structural properties that make preference reasoning tractable. By isolating specific parameters, we can find "islands of tractability" where efficient algorithms exist despite the general-case hardness.

Parameterized Complexity Framework

We analyze the complexity of GCP-nets through five key structural parameters:

  1. Diameter ($k$): The maximum number of "improving flips" required to transition between comparable outcomes.
  2. Condition size ($c$): The maximum number of variables in the antecedent ("if" part) of a preference rule.
  3. Number of rules ($|R|$): The total count of preference rules in the net.
  4. Number of variables ($|V|$): The total number of attributes.
  5. Effect occurrences ($e$): The frequency with which a single variable appears in the consequent ("then" part) of different rules.

The Dominance Problem

The Dominance problem is central to preference reasoning. In GCP-nets, preference is defined by a sequence of improving flips, where each flip changes a single attribute to a more preferred value according to the rules. Since the outcome space is exponential relative to the number of variables, searching for these sequences is typically explosive.

Our analysis reveals that the Dominance problem is Fixed-Parameter Tractable (FPT) when parameterized by the combination of $(k, c)$ or $(k, e)$. We provide a search tree algorithm for the $(k, c)$ case with a runtime of $O^*((k \cdot c + k)^k)$. However, parameterization by diameter ($k$) alone is insufficient, as the problem remains W[1]-complete, suggesting that constraints on the rules themselves are necessary for efficiency.

The Complexity of Diameter

While the diameter $k$ is a crucial parameter for tractability, determining the diameter of a given GCP-net is itself a difficult task.

Definition of the GCP-DIAMETER problem.

We prove that the GCP-DIAMETER problem is PSPACE-complete. If the diameter is guaranteed to be polynomial in the number of variables, the complexity of finding it reduces to $\Pi_2^P$-complete. This suggests that in many practical scenarios, we must rely on proxies or structural constraints rather than calculating the exact diameter.

Empirical Evaluation

To understand how these parameters behave in practice, we conducted an empirical study using randomly generated GCP-nets with 12 variables.

Diameter and average distance vs. number of preference rules for random GCP-nets.

The results indicate that for random instances, the diameter typically scales linearly with the number of variables rather than exponentially. As shown in the figure, the average diameter stabilizes near the number of variables ($|V|=12$) as the number of rules increases. This suggests that the "worst-case" exponential paths may be rare in certain distributions, offering hope for the practical application of our FPT algorithms.

Conclusion

This work provides a roadmap for efficient preference reasoning by identifying the structural boundaries of GCP-nets. While general dominance is PSPACE-complete, combining diameter with rule-based constraints like condition size yields tractable solutions. Future work will explore the Consistency problem and extend these results to multi-valued domains and more complex preference languages.

Summary updated

BibTeX
@inproceedings{kronegger2014parameterized,
  author = {Martin Kronegger and Martin Lackner and Andreas Pfandler and Reinhard Pichler},
  title = {{A Parameterized Complexity Analysis of Generalized CP-Nets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8859},
}
Figure