Computational Problems in Formal Argumentation and their Complexity.

In this paper we give an overview of the core computational problems arising in formal argumentation together with a complexity analysis highlighting different sources of computational complexity. To this end we consider three prominent argumentation formalisms from the literature, that are Dung’s abstract argumentation frameworks, assumption-based argumentation, and abstract dialectical frameworks, each of which allows to highlight different sources of computational complexity in formal argumentation. As most of these problems turn out to be of high complexity we also consider properties of instances, like being in a specific graph class, that reduce the complexity and thus allow for more efficient algorithms. Finally, we also show how to apply techniques from parametrized complexity that allow for a more fine-grained complexity classification.

Authors

• Wolfgang Dvorák TU Wien
• Paul E. Dunne

Keywords

No keywords are indexed for this paper.