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; 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

Project Head Stefan Szeider:

The Parameterized Complexity of Reasoning Problems

Created from the Publication Database of the Vienna University of Technology.