[Back]

W. Dvorak:
"Computational Aspects of Abstract Argumentation";
Supervisor, Reviewer: S. Woltran, P. Dunne; Institut für Informationssysteme, 2012; oral examination: 2012-04-11.

This work is in the context of formal argumentation, a sub-fi eld of Arti cial Intelligence. Probably the most popular formalism in argumentation is abstract argumentation as introduced by Dung. So called abstract argumentation frameworks abstract from the actual con-
tent of arguments and represent them as abstract entities and further abstract from the reasons of conflicts between arguments and represent them as a binary relation. Hence abstract argumentation frameworks can be simply interpreted as directed graphs. On this abstract level one can study the conflicts between arguments and identify coherent sets of arguments. There is a plethora of approaches when a set of arguments should be considered to be coherent, each of these approaches is called a semantics for abstract argumentation.
In every argumentation system, towards conclusions, at some point we have to identify coherent sets of arguments. Hence we identify this as an important computational issue which indeed can be studied on the abstract level. In this work we are doing a computational analysis
of evaluating abstract argumentation frameworks with semantics proposed in the literature.
The fi rst part of this work is devoted to a classical complexity analysis of the associated reasoning problems, using methods from classical complexity theory. We complement existing results and it turns out that most problems are computationally intractable, i.e. NP-hard and in some cases even harder.
In a second part we explore the range of tractable subclasses. We study tractable fragments, i.e. graph classes that allow for an efficient evaluation of the argumentation framework. We extend and complement existing results for acyclic, even-cycle free, symmetric and bipartite Argumentation Frameworks. Moreover we consider the graph parameters tree-width and clique-width to obtain Fixed-Parameter Tractability results. We call a problem fi xed parameter tractable if it can be solved by an algorithm, with a run-time that may highly increase with the value of the parameter for a concrete instance but is polynomial in the size of the instance.
Finally we consider the intertranslatability of diff erent argumentation semantics. We consider a semantic to be translatable to a semantics 0 if there is a (translation) function
modifying frameworks such that semantics on the original framework is in certain correspondence to 0 on the modi ed framework.