Optimisation and Approximation in Abstract Argumentation: The Case of Stable Semantics

Optimisation and Approximation in Abstract Argumentation: The Case of Stable Semantics

Matthias Thimm

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3576-3583. https://doi.org/10.24963/ijcai.2024/396

We analyse two soft notions of stable extensions in abstract argumentation, one that weakens the requirement of having full range and one that weakens the requirement of conflict-freeness. We then consider optimisation problems over these two notions that represent optimisation variants of the credulous reasoning problem with stable semantics. We investigate the computational complexity of these two problems in terms of the complexity of solving the optimisation problem exactly and in terms of approximation complexity. We also present some polynomial-time approximation algorithms for these optimisation problems and investigate their approximation quality experimentally.
Keywords:
Knowledge Representation and Reasoning: KRR: Argumentation
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning