AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
A Parameterized Complexity Analysis of Generalized CP-Nets
Martin Kronegger, Martin Lackner, Andreas Pfandler, Reinhard Pichler

Last modified: 2014-06-21


Generalized CP-nets (GCP-nets) allow a succinct representation of preferences over multi-attribute domains. As a consequence of their succinct representation, many GCP-net related tasks are computationally hard. Even finding the more preferable of two outcomes is PSPACE-complete. In this work, we employ the framework of parameterized complexity to achieve two goals: First, we want to gain a deeper understanding of the complexity of GCP-nets. Second, we search for efficient fixed-parameter tractable algorithms.


Computational social choice; CP-nets; Fixed-parameter tractable algorithms; (Parameterized) complexity theory

Full Text: PDF