A Parameterized Complexity Analysis of Generalized CP-Nets

Martin Kronegger, Martin Lackner, Andreas Pfandler, Reinhard Pichler

AAAI 2014 pp. 1091-1097

doi:10.1609/AAAI.V28I1.8859 /aaai/2014/kronegger2014aaai-parameterized/

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.

PDF AAAI Semantic Scholar

Cite

Text

Kronegger et al. "A Parameterized Complexity Analysis of Generalized CP-Nets." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8859

Markdown

[Kronegger et al. "A Parameterized Complexity Analysis of Generalized CP-Nets." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/kronegger2014aaai-parameterized/) doi:10.1609/AAAI.V28I1.8859

BibTeX

@inproceedings{kronegger2014aaai-parameterized,
  title     = {{A Parameterized Complexity Analysis of Generalized CP-Nets}},
  author    = {Kronegger, Martin and Lackner, Martin and Pfandler, Andreas and Pichler, Reinhard},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2014},
  pages     = {1091-1097},
  doi       = {10.1609/AAAI.V28I1.8859},
  url       = {https://mlanthology.org/aaai/2014/kronegger2014aaai-parameterized/}
}