Talks and Poster Presentations (with Proceedings-Entry):

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.

English abstract:
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

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.