A Parameterized Complexity Analysis of Generalized CP-Nets

Authors

  • Martin Kronegger Vienna University of Technology
  • Martin Lackner Vienna University of Technology
  • Andreas Pfandler Vienna University of Technology
  • Reinhard Pichler Vienna University of Technology

DOI:

https://doi.org/10.1609/aaai.v28i1.8859

Keywords:

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

Abstract

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.

Downloads

Published

2014-06-21

How to Cite

Kronegger, M., Lackner, M., Pfandler, A., & Pichler, R. (2014). A Parameterized Complexity Analysis of Generalized CP-Nets. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8859

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning