On Extension Counting Problems in Argumentation Frameworks

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.