On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

Markus Kröll, Reinhard Pichler, Stefan Woltran

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 1145-1152. https://doi.org/10.24963/ijcai.2017/159

Several computational problems of abstract argumentation frameworks (AFs) such as skeptical and credulous reasoning, existence of a non-empty extension, verification, etc. have been thoroughly analyzed for various semantics. In contrast, the enumeration problem of AFs (i.e., the problem of computing all extensions according to some semantics) has been left unexplored so far. The goal of this paper is to fill this gap. We thus investigate the enumeration complexity of AFs for a large collection of semantics and, in addition, consider the most common structural restrictions on AFs.
Keywords:
Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning
Knowledge Representation, Reasoning, and Logic: Computational models of Argument