On extension counting problems in argumentation frameworks

P. Baroni, P.E. Dunne, M. Giacomin

Proc. of COMMA 2010, 3rd International Conference on Computational Models of Argument, Desenzano del Garda, I, 2010, 63-74

 

Abstract

We consider the problem of counting (without explicitly enumerating) extensions prescribed by multiple-status semantics in abstract argumentation. Referring to Dung’s traditional stable and preferred semantics and to the recently introduced resolution-based grounded semantics (GR*), we show that in general extension counting is computationally hard (actually #P–complete). We then identify non-trivial topological classes of argumentation frameworks where extension counting is tractable. In particular we show, by providing and analyzing the relevant algorithms, that in symmetric argumentation frameworks counting GR* extensions is tractable (but is still hard for stable and preferred estensions), while counting is tractable for all the considered semantics in tree-like argumentation frameworks.

Publisher's on-line resources

Return to publication list