[Back]

J. Fichte, M. Hecher, Y. Mahmood, A. Meier:
"Decomposition-Guided Reductions for Argumentation and Treewidth";
Talk: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada; 2021-08-19 - 2021-08-27; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, {IJCAI} 2021, Virtual Event / Montreal, Canada, 19-27 August 2021", (2021), 1880 - 1886.

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

Knowledge Representation and Reasoning: Computational Complexity of Reasoning Knowledge Representation and Reasoning: Computational Models of Argument Constraints and SAT: Constraint Satisfaction

http://dx.doi.org/10.24963/ijcai.2021/259

Project Head Stefan Woltran:
START