[Back]

W. Dvorak, S. Woltran:
"Technical Note: Complexity of Stage Semantics in Argumentation Frameworks";
Report No. DBAI-TR-2009-66, 2009; 13 pages.

In this work, we answer two questions about the complexity of semi-stable semantics for abstract argumentation frameworks raised by Dunne and Caminada (2008): we show ΙΙP2-completeness for the problem of deciding whether an argument is skeptically accepted, and respectively, ΣP2 -completeness for the problem of deciding whether an argument is credulously accepted under the semi-stable semantics. Furthermore, we extend these complexity bounds to the according decision problems for stage semantics as introduced by Verheij (1997). We also discuss two approaches towards tractability: first, we
prove that the problems under consideration are fixed-parameter tractable with respect to tree-width; second, we show that the problems remain intractable when considering frameworks of bounded cycle-rank.

Project Head Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen