Dvořák, W., Ulbricht, M., & Woltran, S. (2022). Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility. Journal of Artificial Intelligence Research, 74, 1403–1447. https://doi.org/10.1613/jair.1.13603
We study the computational complexity of abstract argumentation semantics based on weak admissibility, a recently introduced concept to deal with arguments of self-defeating nature. Our results reveal that semantics based on weak admissibility are of much higher complexity (under typical assumptions) compared to all argumentation semantics which have been analysed in terms of complexity so far. In fact, we show PSPACE-completeness of all non-trivial standard decision problems for weak-admissible based semantics. We then investigate potential tractable fragments and show that restricting the frameworks under consideration to certain graph-classes significantly reduces the complexity. We also show that weak-admissibility based extensions can be computed by dividing the given graph into its strongly connected components (SCCs). This technique ensures that the bottleneck when computing extensions is the size of the largest SCC instead of the size of the graph itself and therefore contributes to the search for fixed-parameter tractable implementations for reasoning with weak admissibility.
Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds) Extending Methods in Belief Change for a Principled Approach to Advance Dynamics in Argumentation: P30168-N31 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
German Federal Ministry of Education and Research (BMBF)