Decomposition-Guided Reductions for Argumentation and Treewidth
Decomposition-Guided Reductions for Argumentation and Treewidth
Johannes Fichte, Markus Hecher, Yasir Mahmood, Arne Meier
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1880-1886.
https://doi.org/10.24963/ijcai.2021/259
Argumentation is a widely applied framework for modeling and evaluating arguments and its reasoning with various applications. Popular frameworks are abstract argumentation (Dung’s framework) or logic-based argumentation (Besnard-Hunter’s framework). Their computational complexity has been studied quite in-depth. Incorporating treewidth into the complexity analysis is particularly interesting, as solvers oftentimes employ SAT-based solvers, which can solve instances of low treewidth fast. In this paper, we address whether one can design reductions from argumentation problems to SAT-problems while linearly preserving the treewidth, which results in decomposition-guided (DG) reductions. It turns out that the linear treewidth overhead caused by our DG reductions, cannot be significantly improved under reasonable assumptions. Finally, we consider logic-based argumentation and establish new upper bounds using DG reductions and lower bounds.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Computational Models of Argument
Constraints and SAT: Constraint Satisfaction