[Zurück]

U. Endriss, R. de Haan, St. Szeider:
"Parameterized Complexity Results for Agenda Safety in Judgment Aggregation";
Vortrag: International Workshop on Computational Social Choice (COMSOC), Pittsburgh, USA; 23.06.2014 - 25.06.2014; in: "COMSOC 2014", (2014).

Many problems arising in computational social choice are of high computational complexity, and some are located at higher levels of the Polynomial Hierarchy. We argue that a parameterized complexity analysis provides a lot of insight about the factors contributing to the complexity of these problems, and can lead to practically useful algorithms. As a case study, we consider the problem of agenda safety in judgment aggregation, consider several natural parameters for this problem, and determine the parameterized complexity for each of these. Our analysis is aimed at obtaining fixed-parameter tractable (fpt) algorithms that use a small number of calls to a SAT solver. We hope that this work may initiate a structured parameterized complexity investigation of problems arising in the field of computational social choice that are located at higher levels of the Polynomial Hierarchy. A by-product of our case study is the development of complexity-theoretic techniques to provide lower bounds on the number of SAT calls needed by fpt-algorithms to solve certain problems.

http://publik.tuwien.ac.at/files/PubDat_234118.pdf

Projektleitung Stefan Szeider:
Parameterized Compilation

Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems