[Zurück]

R. Pichler, St. Rümmele, St. Szeider, S. Woltran:
"Tractable answer-set programming with weight constraints: bounded treewidth is not enough";
Theory and Practice of Logic Programming, 14 (2014), 2; S. 141 - 164.

We study the computational complexity of problems that arise in ab- stract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given.
- The REPAIR problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set).
- The ADJUST problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument.
- The CENTER problem asks whether, given two extensions of distance k, whether there is a "center" extension that is of distance at most k − 1 from both given extensions.
We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results cover several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.

http://dx.doi.org/10.1017/S1471068412000099

Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems